递归与二叉树

两种思维：遍历视角与子问题视角

这一篇是分岔点

前一篇说了前中后序是三个时刻。这一篇说的是更上一层的东西： 面对一道递归题，你有两种完全不同的组织方式。

  • 遍历视角 —— 我走遍这棵树，一路上用一个外部变量把答案攒出来。递归函数不返回值。
  • 子问题视角 —— 我让递归函数返回一个答案，然后用子树的答案拼出当前的答案。

⭐ 这不是风格偏好。它是后面两章的分岔点： 遍历视角往下走是回溯与 DFS，子问题视角往下走是分治与动态规划。 现在把这个分野想清楚，后面两章就只是在填细节。

同一道题，两种写法

求二叉树的最大深度。

遍历视角：我走遍每个节点，随身带一个「当前走到第几层」的变量， 一路记录见过的最大值。

function maxDepth(root) {
  let res = 0;
  let depth = 0;                 // 外部变量：当前所在的层数

  function traverse(node) {
    if (node === null) return;   // 注意：不返回任何值

    depth++;                     // 前序位置：踏进这个节点
    res = Math.max(res, depth);

    traverse(node.left);
    traverse(node.right);

    depth--;                     // 后序位置：离开这个节点
  }

  traverse(root);
  return res;
}

子问题视角：一棵树的深度 = 1 + 两棵子树深度的较大者。

function maxDepth(root) {
  if (root === null) return 0;
  // 相信定义：这两个调用各自返回了子树的深度
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

两段代码解同一道题，长度差三倍，思路完全不同。

🚨 遍历视角里那个 depth--

这是遍历视角唯一容易错的地方，也是它最重要的一处。

depth 是共享的：整个递归过程只有这一个变量。进入一个节点时 depth++， 离开时必须 depth-- 还原，否则右子树会带着左子树留下的层数继续往下加。

这两个错法的症状很不一样，而且各自有一整类形状测不出来。 下面的结论是穷举 n=1~9 的全部 6917 种树形得到的，不是抽样：

错法一｜漏掉 depth--。 答案恒等于节点数（6917 种树形无一例外）—— 因为 depth 只增不减，走完最后一个节点时它正好等于走过的节点数。

⚠️ 于是它在任何「每个节点最多一个孩子」的形状上都是对的 （链、单边的歪树……那时高度本来就等于节点数，穷举确认：这类形状上错 0 个）。 ⭐ 「树越宽偏得越离谱」成立，而且能量化：满二叉树高 6 时答案 63、正确 6，10.5 倍。

错法二｜depth-- 放在两个 traverse 中间（不是后序位置）：

满二叉树   高 1~8 偏差**恒为 0**   ← 完全测不出来
全右链     正确 n，它恒返回 **1**  ← 错得最狠
全左链     完全正确

🚨 所以「它在满二叉树上表现得很轻微」这个说法是不对的 —— 在满二叉树上它 一点误差都没有。原因是左右对称：res 已经被左子树拉到正确值， 右子树少算的那一层刚好被盖住。 而在全右链上，每一层都少算一层、层层累积，最后恒为 1。 （全左链正确是因为那个 depth-- 之后再没有任何 traverse 会用到 depth。）

📌 判据比记症状有用：这一句错在「右子树的起始层数」上， 所以要暴露它，用例必须有右孩子、而且左右不对称。 用满二叉树自测这一句，等于没测。

⭐ 「进入时做选择、离开时撤销」这一对操作，就是回溯算法的全部内容。 你在这里已经写过一遍回溯了，只是还没给它起名字。

怎么选

判据只有一条：

能不能用子问题的答案，拼出原问题的答案？

能 → 子问题视角，让函数返回值。 只能靠走遍所有情况才知道 → 遍历视角，用外部变量收集。

拿几道常见题套一下：

题目 视角 为什么
最大深度 都行 深度可以由子树深度拼出来
翻转二叉树 子问题 翻转左右子树后交换即可
二叉树的直径 混合 见下
所有根到叶的路径 遍历 「路径」是走出来的，不是拼出来的
全排列 / 子集 遍历 同上，要的是过程不是结果值
判断是否为平衡树 子问题 由子树高度和平衡性拼出来

📌 「要路径」几乎总是遍历视角。 路径是一条走过的轨迹， 它天然存在于「走」的过程里，没法由子树的返回值组合出来。

混合：直径那道题其实用了两个视角

回看上一篇的直径解法：

function diameterOfBinaryTree(root) {
  let maxD = 0;

  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 用子问题视角算深度，maxD 用遍历视角收集答案。

之所以要混，是因为「直径」这个量不满足上面那条判据 —— 一棵树的直径不能由左右子树的直径直接拼出来（最长路径可能横跨根节点， 也可能整个藏在某棵子树里）。但深度可以拼。 于是就借深度这趟递归，顺路把每个节点处的候选答案记下来。

⭐ 这是一个很常用的套路：返回值算一个能拼的量，外部变量收集那个不能拼的答案。 「二叉树中的最大路径和」用的是同一招。

进阶：让返回值一物两用（最近公共祖先）

上面所有例子里，返回值都是一个量（深度、是否平衡）。 最近公共祖先这道题把子问题视角推到了另一个方向： 返回值是一个节点，而且它有两种含义。

题意：给定树中的两个节点 p、q，找最深的那个同时是二者祖先的节点。

function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;    // 两边各找到一个 → 当前节点就是答案
  return left ?? right;              // 只有一边有 → 把它原样往上报
}

🚨 这个函数的返回值有两种含义，靠调用方分不清 —— 也不需要分清。

情况 返回的是
子树里只有 p（或只有 q） 那个节点本身
子树里 p、q 都有 它们的 LCA
子树里一个都没有 null

⭐ 这看起来像个设计缺陷，实际是这道题最漂亮的地方。 关键在于题目保证 p 和 q 都在树中：既然都在，那么「只在一边找到了东西」 就必然意味着「另一个也在那一边」——于是原样上报是对的， 而第一次出现「两边都非空」的那个节点，必然是最深的公共祖先。

⚠️ 这条推理完全依赖那个前提。把前提去掉（比如 q 根本不在树里）， 它不会报错、也不会返回 null，而是恒定返回 p 自己：

p 在树中 ⇒ 递归必然走到 p，由 base case 返回 p； q 不在树中 ⇒ 每个节点的另一侧恒为 null ⇒ left && right 永不成立 ⇒ p 被原样一路上报到根。

这是能推出来的确定结论，不是统计出来的倾向 （穷举 n=1~8 的全部树形 × 全部 p 共 15521 个用例，返回 p 的 15521 个、 返回别的节点 0 个、返回 null 0 个）。 🚨 而 p 恰恰是一个完全合法的 LCA 取值（当 q 在 p 的子树里时答案就是 p）， 所以返回值的形状和「真的找到了」一模一样，调用方无从区分。 📌 面试里被追问「如果不保证两个都存在呢」，答案是得多带一个信息 （比如返回 [节点, 找到几个]），不是改判断条件。

两个真会错的写法

拿「求根到 p、根到 q 的两条路径、取最后一个公共节点」这个笨办法当参考模型。

先说 ①：去掉 root === p || root === q 这个 base case。 它彻底不工作 —— 永远返回 null，任何用例一测就发现（对拍 20000 组，错 20000 组）。

② 把 left && right 写成 left || right（只有一边有时也返回 root）才是 危险的那个。它的出错条件不是概率性的，穷举出来是个充分必要条件：

② 出错 ⟺ 真正的 LCA 不是根节点。

穷举 n=2~7 的全部 624 种树形 × 全部 23020 个 (p, q) 对： 「LCA 是根却答错」0 例，「LCA 不是根却答对」0 例。

⚠️ 于是「② 的出错率是多少」这个问题没有唯一答案 —— 它等于「LCA 不是根」的比例，而那完全取决于你拿什么树去测：

随机树（节点数 2~12，随机挂空位）   约 37%
穷举 n=2~7 的全部树形               58%

📌 这也是为什么它危险：随手画一棵小树、挑两个分居左右子树的节点， LCA 就是根，它答对。而这恰恰是大多数人自测时会画的那个用例。

🚨 一个曾经写在这里的错误归因，值得留下来当反面例子。 原先这一节写的是「它错的组里有 5191 组属于『一个是另一个的祖先』， 而这种情形在随机树里占到 64.4%，是主流而不是边角」—— 听起来像是找到了原因，实测却不成立：

出错率
「一个是另一个的祖先」 61.5%
两者互不为祖先 45.5%

两者都远离 0% 和 100%，祖先关系根本不是判据。 它只是和真判据相关：p、q 成祖先关系时，LCA 就是那个祖先节点， 它「不是根」的可能性更大 —— 是个混淆变量，不是原因。 ⭐ 判据：一个「原因」如果不能把出错率分成 0% 和 100%， 它就还不是原因，只是一个相关量。

那个提前返回是剪枝，不是必需

root === p || root === q 这一句写在前序位置（一进入就判断）， 撞上目标就不再往下搜了。我以为把它挪到后序位置会出错，实测结果完全一样：

// 挪到后序，一样对，只是不剪枝
const left = f(root.left, p, q), right = f(root.right, p, q);
if (left && right) return root;
if (root === p || root === q) return root;
return left ?? right;

差别只在访问次数（30 个节点的树，各 3000 轮；数的是函数调用次数， 含 root === null 那次 —— 所以走遍全树是 30×2+1 = 61）：

树的形状 前序提前返回 后序版 省下
随机 41.8 次 61.0 次 31.4%
链状 19.4 次 61.0 次 68.2%

⚠️ 这里的「链状」别读成「最坏情况」（这一行以前就是这么标的）。 后序版恒为 61，跟形状无关；而对前序版，链状是最省的形状 —— 链上任何一个节点都把整棵树切成「上面」和「下面」，撞到 p 就能剪掉一大段。 👉 对剪枝来说，退化的树反而是它表现最好的地方。

⭐ 结论：它是个剪枝。找到 p 之后，p 的整棵子树都不用再搜 —— 因为答案要么是 p 自己（q 在它下面），要么在更上面。 📌 分清「这一句去掉会算错」和「这一句去掉会变慢」很重要。 栈与队列那篇里两个栈实现队列的 if 属于前者（去掉直接算错），这里属于后者。

往后看

  • 遍历视角 → 回溯算法与 DFS。关注的是路径：走到哪、做了什么选择、怎么撤销。
  • 子问题视角 → 分治与动态规划。 关注的是返回值：子问题的答案怎么合并成原问题的答案。

动态规划那一篇里「暴力递归 → 备忘录 → 递推」的推导路径， 起点正是这里的子问题视角 —— 先写一个返回值正确的递归函数，再优化它。

练习

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

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