递归与二叉树

二叉树的原理与前中后序

为什么二叉树是枢纽

先说清楚这一章的分量：后面几乎所有算法都是二叉树递归的变形。

  • 回溯算法 = 在多叉树上做遍历，多了「撤销选择」
  • DFS = 同一棵树，做选择的位置换了一处
  • 动态规划 = 递归树上把重复的子问题记下来
  • BFS = 二叉树的层序遍历，换到图上
  • 图的遍历 = 二叉树的遍历，多了一个 visited

所以这一章别赶进度。省下的时间会在后面加倍还回去。

前中后序：三个时刻，不是三种算法

先看这个框架：

function traverse(root) {
  if (root === null) return;

  // ← 前序位置

  traverse(root.left);

  // ← 中序位置

  traverse(root.right);

  // ← 后序位置
}

⭐ 前中后序不是三段独立的代码，是同一次遍历中的三个时间点。 一次遍历里，每个节点都会被经过三次：进入它的时候、左子树处理完的时候、 右子树也处理完的时候。你的代码写在哪个位置，就是选择在哪个时刻做事。

所谓「前序遍历」，不过是把打印语句放在了前序位置。

这三个位置的能力不一样

这才是重点，也是这一节唯一需要记住的东西：

位置 你手上有什么
前序 只有从根传下来的信息（参数）
中序 加上左子树的结果
后序 左右子树的结果都有了

👉 所以判据很简单：当前节点需要子树的信息才能算，就必须写在后序位置。

⚠️ 写错位置的症状不是报错，是答案不对或者复杂度爆炸， 而代码看起来完全正常。下面这个例子就是。

例：二叉树的直径

直径 = 任意两个节点之间最长路径的长度。这条路径不一定经过根节点。

关键观察：经过某个节点的最长路径 = 它左子树的深度 + 右子树的深度。 需要子树的深度 → 必须在后序位置算。

function diameterOfBinaryTree(root) {
  let maxD = 0;

  // 定义：depth(node) 返回以 node 为根的子树的深度
  function depth(node) {
    if (node === null) return 0;
    const l = depth(node.left);
    const r = depth(node.right);

    // 后序位置：左右子树的深度都已经算出来了
    maxD = Math.max(maxD, l + r);

    return 1 + Math.max(l, r);
  }

  depth(root);
  return maxD;
}

🚨 常见的错法是在前序位置写：对每个节点各调一次 depth(左) 和 depth(右)， 再取最大值。结果是对的，复杂度却从 O(n) 退化到 O(n²) —— 因为每个节点都要重新遍历自己的整棵子树去求深度。

实测（500 棵随机树对拍，两版答案 0 处不一致 —— 确实「结果是对的」）， 数一下访问节点的次数：

树的形状 n 后序版 前序版 倍数
链状 100 100 4,950 49.5×
链状 400 400 79,800 199.5×
链状 1,600 1,600 1,279,200 799.5×
平衡 100 100 480 4.8×
平衡 400 400 2,698 6.7×
平衡 1,600 1,600 13,964 8.7×

⭐ 链状那三行是 O(n²) 的指纹：n 翻两番，倍数也翻两番（49.5 → 199.5 → 799.5）。 而平衡树上它只退化到 O(n log n)（倍数从 4.8 缓慢涨到 8.7），没那么惨 —— 同一个 bug，在不同形状的树上严重程度差两个数量级。

⚠️ 而 7 个节点的小样例：后序 7 次 vs 前序 10 次，只差 1.4×。 肉眼、单元测试、小样例全都看不出来，只有数据量上去才超时。

⭐ 这就是「位置决定能力」的价值：把计算挪到后序位置， 深度这个信息在递归返回时顺手就带上来了，不用重新算。

中序位置的专属场景：BST

对二叉搜索树（BST）来说，中序位置有一个别处没有的性质：

中序遍历 BST，得到的是升序序列。

原因直接来自 BST 的定义 —— 左子树全部小于根，右子树全部大于根。 中序的顺序正好是「左 → 根 → 右」，也就是「小 → 中 → 大」。

function inorder(root, out = []) {
  if (root === null) return out;
  inorder(root.left, out);
  out.push(root.val);      // 中序位置
  inorder(root.right, out);
  return out;
}

📌 一大批 BST 题的解法就是「中序遍历 + 在中序位置做点事」： 找第 k 小、验证是否为合法 BST、把 BST 转成累加树。 遇到 BST 先想中序，命中率很高。

深度与翻转：两种思维的预告

同一道题，前序和后序常常各有一种写法。以翻转二叉树为例：

// 后序位置：左右子树都翻转好了，再交换它们
function invertTree(root) {
  if (root === null) return null;
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}
// 前序位置：先交换，再分别去翻转两棵子树
function invertTree(root) {
  if (root === null) return null;
  [root.left, root.right] = [root.right, root.left];
  invertTree(root.left);
  invertTree(root.right);
  return root;
}

两种都对 —— 1000 棵随机树对拍，两版结果0 处不一致。

⭐ 但它们的差别不只是顺序，背后是两种不同的思考方式， 下一篇两种思维专门讲这个分野， 它决定了后面两章的走向。

📌 顺带一提，上面那条「中序遍历 BST 得到升序」也验过： 1000 棵随机 BST，中序结果与排序后的值数组逐棵一致，0 棵例外。

迭代遍历：知道就行

用显式栈也能遍历，不占调用栈：

function preorderIterative(root) {
  const res = [], stack = [];
  if (root) stack.push(root);
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    // 🚨 先压右再压左 —— 栈是后进先出，这样弹出时才是「左先右后」
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
}

🚨 那句「先压右再压左」写反的症状很干净。同一棵树：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

递归前序        [1, 2, 4, 5, 3, 6, 7]
迭代（先压右）  [1, 2, 4, 5, 3, 6, 7]   ✅ 一致
迭代（先压左）  [1, 3, 7, 6, 2, 5, 4]   ← 写反

⭐ 写反得到的是**「根右左」，恰好是前序的镜像 —— 不是乱序，是另一种合法的遍历。 所以它看起来很像对的**，只有跟正确答案逐位比才发现。

⚠️ 前序的迭代版很短，中序和后序要麻烦得多（后序通常靠「前序改右左顺序再整体反转」绕过去）。 📌 上面那个「根右左」正是这个技巧的一半：把它整体反转就是后序。写反的那版不是废品，是后序的中间步骤。

👉 面试里几乎只考前序的迭代版，以及「你知不知道可以用栈改写」这件事本身。 把递归写利索，比背下三套迭代模板划算。真正需要迭代的场合只有一个： 树退化成链、深度到了万级 —— 那时候递归会栈溢出（见怎么理解递归）。

下一步

上面三种遍历做的都是「树 → 序列」。反过来问：给定序列，能不能把树还原回来？ —— 由遍历序列反推二叉树。

📌 那一篇的支点是：前序和后序负责「指认根」，中序负责「分开左右」， 两个职责缺一不可 —— 所以「前序 + 后序」这个看着信息量更大的组合反而不够。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。