最近公共祖先 图解题解

最近公共祖先到底是什么

给定二叉树中的两个节点 p 和 q，最近公共祖先（LCA）是同时罩住两者、且层级最深的那个节点。有一个容易忽略的定义细节：节点可以是它自己的祖先——如果 p 本身就在 q 的上方，那 p 自己就是答案。这个细节直接决定了递归里「碰到 p 或 q 就立刻返回」这一步是安全的。

为什么不先求两条路径再比对

最直觉的做法是分别找出根到 p、根到 q 的两条路径，再从头对比，最后一个相同的节点就是 LCA。这个思路完全正确，但要遍历两趟、还要额外存两条路径。它的价值在于点破了问题的本质：LCA 就是两条根到目标路径的分岔点。递归解法的妙处，是把「找路径」和「比路径」压进同一趟遍历里完成。

递归函数的返回值到底代表什么

递归函数的语义是：在当前子树里搜索 p 和 q，返回找到的东西。结果只有三种：子树里一个目标都没有，返回空；只找到 p 和 q 中的一个，就把那个节点往上传；两个都在这棵子树里，返回它们的 LCA。递归时碰到空或者碰到 p、q 本身就直接返回自己——即使另一个目标还藏在它下面也没关系，因为那种情况当前节点本来就是两者的公共祖先，返回自己恰好正确。

为什么左右都非空时当前节点就是答案

按后序的方式先问左子树、再问右子树，两边的答案都拿到后再裁决。若左右各返回一个非空节点，说明 p、q 分居当前节点的两侧，这里是两条向上路径第一次汇合的位置；任何更深的节点都不可能同时罩住分居两边的目标，所以当前节点就是最近的那个公共祖先。若只有一边非空，说明目标（或已经在下面算出的 LCA）全在那一边，原样上传即可；两边都空就传空。

这也解释了为什么必须是后序遍历：父亲的裁决完全依赖左右孩子的搜索结果，孩子不先算完，父亲无从判断。

复杂度多少，还有哪些追问

每个节点恰好被访问一次，时间 O(n)；递归栈深等于树高 h，平衡树是 O(log n)，最坏退化成链是 O(n)。

两个常见追问：若不保证 p、q 都在树里，要在后序里额外用两个布尔量确认两者真的都被找到，否则交汇点不算数；若树是二叉搜索树（LeetCode 235），可以利用有序性从根往下走——p、q 都比当前小就走左，都比当前大就走右，第一次分居两侧的节点即 LCA，只需 O(h) 且不必搜索两边。

Python

def lowestCommonAncestor(root, p, q):
    if root is None or root is p or root is q:
        return root            # 命中目标或到底，原样返回
    left  = lowestCommonAncestor(root.left,  p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root            # 左右各找到一个 → 当前就是 LCA
    return left if left else right   # 否则往有的那边上传

C++

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q){
    if(root == nullptr || 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;   // 分居两侧，当前即 LCA
    return left ? left : right;       // 往有的那边上传
}

Java

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; // 分居两侧 → LCA
    return left != null ? left : right;             // 往有的那边上传
}