二叉树与递归 - 总结

心智模型

解决二叉树问题的一个通用心法

把两边节点都看成黑盒，而避免考虑太多细节陷进去。

我们仅在根节点、左黑盒、右黑盒三个东西里考虑问题。

递归函数其实是一个可复用的模式，想清楚设计一个模式对所有节点都适用。

最后考虑一下边界情况，如递归到最深处会怎样。

一些优化思路：

内部创建的函数，如果用到了外部变量，是否可以优化成纯函数？
是否有不需要搜索的地方，可以短路、剪枝？（这通常可以在返回值里做手脚）

特殊的二叉树

二叉搜索树

二叉搜索树严格遵循左子树 > 根节点 > 右子树，且该性质在深层也得成立。

中序遍历是严格递增序列

二叉搜索树的 中序遍历 序列是严格递增的。

也就是说，假设我们用一个 prevVal 值记录遍历过程中的每个值，那么后一个 prevVal 必然大于前一个，可以利用这个性质来验证一棵树是不是二叉搜索树。

此外，由于有一个严格递增序列，我们甚至可以用 Generator 生成器配合 yield* 等处理成惰性序列来解决问题。

二叉树的遍历

前序遍历（preOrder）：根，左，右
中序遍历（inOrder）：左，根，右
后序遍历（postOrder）：左，右，根

通过遍历序列构建二叉树

给定前中、中后序列的情况下，我们都能构建出唯一的二叉树。

但是只给前、后序列的情况下，除非二叉树是满二叉树，否则我们不能保证答案唯一。

解决这类问题一个通用模板如下：

下面这段代码可以在给定前、中序列的情况下，构建出二叉树

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const indexMap = new Map<number, number>();
  for (let i = 0; i < inorder.length; i++) indexMap.set(inorder[i], i);

  let preIndex = 0;

  function dfs(left: number, right: number) {
    if (left > right) return null;

    const rootVal = preorder[preIndex++];
    const root = new TreeNode(rootVal);

    const mid = indexMap.get(rootVal)!;

    root.left = dfs(left, mid - 1);
    root.right = dfs(mid + 1, right);
    
    return root;
  }
  return dfs(0, inorder.length - 1);
}

这个解法的时空复杂度都是 O(n) ，解法有几个关键：

index 和 rootVal 的取值

例如在前中的情况下，我们令 preIndex = 0 ，并且每次递增来取 rootVal 。这是因为前序遍历的顺序本身就是根、左、右，下面又是先设置 root.left，所以递增自然解决问题。

如果是中后的情况，我们就需要这样：

1
2
3

let postIndex = length - 1;
// ...
	const rootVal = postorder[postIndex--];

并且后面还必须先遍历右序列：

1 2	root.right = dfs(mid + 1, right); root.left = dfs(left, mid - 1);

这是因为，在中后序列的情况下，根节点出现在后序遍历序列的尾部。所以，我们倒着来，让 postIndex 每次递增。从左、右、根变成了根、右、左。那么，自然是先根再右了。
分析这个 postIndex 的走向，能帮我们知道到底应该先遍历哪里。

left 和 right 边界的设置

说白了，我们总是要去找一个分割点，以此分割出左子树和右子树。

有中序遍历的情况下都差不多，但是如果只有前序和后序，那会变成这样：

1
2
3

const postIndex = map.get(preorder[preIndex]);
root.left = dfs(left, postIndex);
root.right = dfs(postIndex + 1, right - 1);

其中 map 是后序遍历的数组转成的 map。

这里的 right - 1 设置的比较精髓，原因在于因为后序遍历的最后一个节点是根，所以 right 就是根，那么 right 的前一个自然就是右子树的右边界了。

二叉树的层序遍历

下面这段代码用来解决 102. 题，其能输出一个每一层二叉树节点值的数组

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const ans: number[][] = [];
  const queue = [root];
  while (queue.length) {
  // 关键：每一层循环的次数靠此固定
    const n = queue.length;
    const temp: number[] = [];
    for (let i = 0; i < n; i++) {
      const node = queue.shift()!;
      temp.push(node.val);
      node.left && queue.push(node.left);
      node.right && queue.push(node.right);
    }
    ans.push(temp);
  }
  return ans;
}

层序遍历的关键是用队列这个数据结构。

队列是一种先进先出的数据结构，我们在 JS 里用数组模拟队列。

最开始队列里我们只需要放一个 root 节点：

1	const queue = [root]

之后把队列里的元素依次取出，每次取出又把取出的节点的左右节点推进队列。

为了确知每一次要操作多少个节点，我们需要每一次都用一个常量来记录队列内的元素数。

1	const n = queue.length

Leaves' blog