236. 二叉树的最近公共祖先 (js)

题目描述

236. 二叉树的最近公共祖先

关键思路

如何确保找到的是最近的公共祖先？

关键点1：后序遍历 + 自底向上

• 遍历顺序是左 → 右 → 根（后序），

• 递归是从叶子节点“向上”返回的。

• 所以我们第一次在某个节点发现 p 和 q 分别在左右子树时，这个节点就是最底层的祖先，也就是最近的。

关键点2：只有第一次满足 left && right 才返回该节点

• 一旦某个节点返回了 left && right，说明：

  • 它的左边找到了一个（比如 p），

  • 它的右边找到了另一个（比如 q），

  • 所以自己就是“分叉点”，再往上找也是祖先，但就不是“最近”的了。

  • 如果上层节点也满足 left && right，说明它是一个“更远的祖先”，但我们已经在底层返回了“最近”的；

• 我们只返回这第一个分叉点作为最终答案。

• 这个返回值会一级一级地向上传递，最终在 root 返回。

举个例子：

        A
       / \
      B   C
     / \
    D   E
       /
      F

设 p = D，q = F。

D 和 F 分别出现在节点 B 的左子树和右子树；

所以 B 是 D 和 F 的最近公共祖先；

A 虽然也是祖先，但距离更远。

递归过程如下：

dfs(D) → 返回 D

dfs(F) → 返回 F

dfs(B) → 得到 left = D，right = F，所以返回 B

dfs(A) → 左边返回了 B，右边返回了 null，最终返回 B

最终结果是 B，是最近的公共祖先。

想清楚这个问题，也就明确了递归的终止条件和递归返回值的含义，本质上就是一个后序遍历的 dfs。

• 返回值的含义：
  • 每次返回值代表当前节点为根的子树中，是否包含 p 或 q，或它们的最近公共祖先。
  • 如果返回非空，就代表这棵子树“有贡献”。
• 递归终止条件：
  • node === null 当前子树是空的，表示什么都没找到，返回 null，终止这条分支的递归。
  • node === p || node === q：找到了目标节点之一（p 或 q），直接返回当前节点。这个信息将被上传给上层函数，用于判断祖先位置。

完整代码

var lowestCommonAncestor = function (root, p, q) {
    function postorder(node, p, q) {
        if (node === null || node === p || node === q) {
            return node;
        }
        let nodeLeft = postorder(node.left, p, q);
        let nodeRight = postorder(node.right, p, q);
        if (nodeLeft && nodeRight) {
            return node;
        }
        return nodeLeft !== null ? nodeLeft : nodeRight;
    }
    return postorder(root, p, q);
};