lqj1 / front_end_notebook Goto Github PK

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算法秘籍》