1、是否可以通过遍历⼀遍⼆叉树得到答案?如果可以,⽤⼀个 traverse 函数配合外部变量来实现,这叫 「遍历」的思维模式。 2、是否可以定义⼀个递归函数,通过⼦问题(⼦树)的答案推导出原问题的答案?如果可以,写出这个递归 函数的定义,并充分利⽤这个函数的返回值,这叫「分解问题」的思维模式。
-
⽆论使⽤哪种思维模式,你都需要思考:
- 如果单独抽出⼀个⼆叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?其他的节点不⽤ 你操⼼,递归函数会帮你在所有节点上执⾏相同的操作。
-
举例
- 快速排序就是个⼆叉树的前序遍历,归并排序就是个⼆叉树的后序遍历
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/************************/
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
- 先构造分界点,然后去左右⼦数组构造分界点,你看这不就是⼀个⼆叉树的前序遍历吗。
- 再说说归并排序的逻辑,若要对 nums[lo..hi] 进⾏排序,我们先对 nums[lo..mid] 排序,再对nums[mid+1..hi] 排序,最后把这两个有序的⼦数组合并,整个数组就排好序了
// 定义:排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
// 排序 nums[lo..mid]
sort(nums, lo, mid);
// 排序 nums[mid+1..hi]
sort(nums, mid + 1, hi);
/****** 后序位置 ******/
// 合并 nums[lo..mid] 和 nums[mid+1..hi]
merge(nums, lo, mid, hi);
/*********************/
}
-
前中后序是遍历⼆叉树过程中处理每⼀个节点的三个特殊时间点,绝不仅仅是三个顺序不同的 List:
- 前序位置的代码在刚刚进⼊⼀个⼆叉树节点的时候执⾏; 后序位置的代码在将要离开⼀个⼆叉树节点的时候执⾏; 中序位置的代码在⼀个⼆叉树节点左⼦树都遍历完,即将开始遍历右⼦树的时候执⾏。
-
为什么多叉树没有中序位置
- 因为⼆叉树的每个节点只会进⾏唯⼀⼀次左⼦树切换右⼦ 树,⽽多叉树节点可能有很多⼦节点,会多次切换⼦树去遍历,所以多叉树节点没有「唯⼀」的中序遍历位置。
-
⼆叉树的所有问题,就是让你在前中后序位置注⼊巧妙的代码逻辑,去达到⾃⼰的⽬的,你只需要单独思考 每⼀个节点应该做什么,其他的不⽤你管,抛给⼆叉树遍历框架,递归会在所有节点上做相同的操作。
- ⼆叉树题⽬的递归解法可以分两类思路,
- 第⼀类是遍历⼀遍⼆叉树得出答案,
- 第⼆类是通过分解问题计算出答案,
- 这两类思路分别对应着 回溯算法核⼼框架 和 动态规划核⼼框架
1、是否可以通过遍历⼀遍⼆叉树得到答案?如果可以,⽤⼀个 traverse 函数配合外部变量来实现。 2、是否可以定义⼀个递归函数,通过⼦问题(⼦树)的答案推导出原问题的答案?如果可以,写出这个递归 函数的定义,并充分利⽤这个函数的返回值。 3、⽆论使⽤哪⼀种思维模式,你都要明⽩⼆叉树的每⼀个节点需要做什么,需要在什么时候(前中后序)做。
- 只有后序位置才能通过返回值获取⼦树的信息。 那么换句话说,⼀旦你发现题⽬和⼦树有关,那⼤概率要给函数设置合理的定义和返回值,在后序位置写代码了。
- 《labuladong算法秘籍》