最近公共祖先 图解题解

这道题到底在问什么

树

3 的左右是 5 和 1；5 的左右是 6 和 2

p, q

6, 2

输出

5

最优解：一步一步想明白

1. 3最直觉的做法：先走一遍求出根到 p 的路径，再走一遍求出根到 q 的路径，然后把两条路径从头逐个比，最后一个相同的节点就是答案。能对，但要存两条路径、走两遍、再对齐比一遍，又费空间又啰嗦。
2. 4转折来了：不必显式存路径。dfs(node) 碰到空、或碰到 p、或碰到 q，就把自己往上返回；否则先递归左右孩子，谁找到目标谁就把目标往上传。某个节点如果左右两边各传回一个非空，说明 p、q 分居它的两侧，它就是 LCA。要等左右消息都回来才能判，所以用后序。
3. 5目标已标蓝：p=6, q=2从根 3 进入，它现在是橙色当前节点。3 不是 p 也不是 q，不能马上决定，得先递归左右、等它们汇报。蓝色的 6 和 2 就是要找的 p、q。先往左孩子 5 走。
4. 6dfs(5)：5 也不是目标走到节点 5，它变成橙色当前节点。5 本身不是目标，同样得先问左右孩子 6 和 2。先往左孩子 6 下探。
5. 7dfs(6) 命中 → return 6走到节点 6，它就是 p，命中。6 变绿，立刻把自己返回上去，不再往下递归。于是 5 的左边收到一个非空结果，记作 L 等于 6。
6. 8dfs(2) 命中 → return 2回到 5，再走右孩子 2，它是 q，命中。2 变绿、返回 2。现在 5 手里两边都有了：左 L 等于 6、右 R 等于 2，两侧都非空。这正是「分叉」的信号。
7. 9L=6 且 R=2 都非空 → 5 是分叉点把镜头停在节点 5：它左边收到 6、右边收到 2，两个都不是空。这说明 p、q 一边一个，分居 5 的两侧。判定成立——5 就是最近公共祖先。这一帧就是整题的核心：第一个左右都收到非空的节点。
8. 105 是 LCA → return 5 给 35 被判定为 LCA 后，把「自己」当作结果返回给父亲 3，成为 3 的左结果 L 等于 5。但 3 还不能下结论，必须把右孩子 1 也问完，才知道 3 会不会又是一个分叉点。
9. 11dfs(1) 左右皆空 → return None再看 3 的右孩子 1，它现在是橙色当前节点。递归进它的子树 0 和 8，里面既没有 6 也没有 2，左右都返回 None。所以 dfs(1) 也返回 None。这是「这一侧什么都没找到」的负分支。
10. 12L=5, R=None → 不分叉，return 5最后回到根 3，它左边收到 5、右边收到 None。不是两侧都有，所以 3 不是分叉点，它只把非空那一侧的 5 原样往上传。最终答案就是 5。可见 LCA 就是「两侧汇合」的最低那个点。
11. 15后序遍历就是「子树先把消息报上来，父节点再汇总」。每个节点上报「我子树里找到了谁」，第一个同时从左右收到目标的节点就是 LCA。这套汇报思路也用在带父指针的 LCA、BST 版 LCA 上。
12. 17错写：左边非空就 return node换个例子想想：如果 q 改成 8、在右支里。走到 5 时，它左边收到 6、右边是 None。正确做法是只把 6 上传，让 3 去汇合 6 和 8。但若错写成「左边非空就 return 5」，就会把 5 当答案，漏掉真正的分叉点 3。所以一定要左右都非空才行。
13. 21把这题练到能复述后，再去同类题迁移：LC235 的 BST 版 LCA 用有序性更省；LC1650 给了父指针可以转成链表相交。点开右侧的「二叉树」专题继续刷，写不出来时让 AI 助教小欧带你拆解。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) return root;
        return left ? left : right;
    }
};

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

def dfs(node):
    # 1) 出口：空 或 命中目标 → 返回自己
    if not node or 命中(node):
        return node
    L = dfs(node.left)        # 2) 左右都递归
    R = dfs(node.right)
    if L and R:               # 3) 都非空 → 当前是分叉点
        return node
    return L or R             # 4) 否则上传非空那一侧

TreeNode* dfs(TreeNode* node, TreeNode* p, TreeNode* q) {
    // 1) 出口：空 或 命中目标 → 返回自己
    if (!node || node == p || node == q) return node;
    TreeNode* L = dfs(node->left, p, q);   // 2) 左右都递归
    TreeNode* R = dfs(node->right, p, q);
    if (L && R) return node;               // 3) 都非空 → 分叉点
    return L ? L : R;                      // 4) 否则上传非空侧
}

TreeNode dfs(TreeNode node, TreeNode p, TreeNode q) {
    // 1) 出口：空 或 命中目标 → 返回自己
    if (node == null || node == p || node == q) return node;
    TreeNode L = dfs(node.left, p, q);     // 2) 左右都递归
    TreeNode R = dfs(node.right, p, q);
    if (L != null && R != null) return node; // 3) 都非空 → 分叉点
    return L != null ? L : R;              // 4) 否则上传非空侧
}

复杂度

面试官可能追问