如何求二叉树中两个节点的最近公共祖先（LCA）？

简化版

最近公共祖先（LCA）是「同时是 p 和 q 祖先的、深度最大的那个节点」。对普通二叉树，用后序递归：在当前节点，分别去左右子树找 p、q。若 p、q 分别在左右两侧，当前节点就是 LCA；若两者都在同一侧，LCA 就在那一侧。递归回溯时第一个「左右都命中」的节点即答案。O(n)。

详细版

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;  // p、q 分居两侧 → 当前是 LCA
    return (left != null) ? left : right;             // 都在一侧，返回非空那侧
}

递归函数的语义：「在以 root 为根的子树里，找到 p 或 q 就返回它，找不到返回 null」。

若某节点的左右递归结果都非空，说明 p、q 一个在左、一个在右，这个节点就是 LCA。
若只有一侧非空，说明 p、q 都在那一侧（或只找到一个），把该结果继续往上传。

完整版教学

一、什么是 LCA

两个节点 p、q 的公共祖先是「既是 p 的祖先、又是 q 的祖先」的节点（一个节点也可以是自己的祖先）。最近公共祖先是所有公共祖先中深度最大、离它俩最近的那个。直观说，就是从 p 和 q 分别往根走，两条路径第一次汇合的节点。

二、递归解法的核心：函数语义

这题的关键是想清楚递归函数「返回什么」。定义 lca(root, p, q) 为：在 root 子树中，如果找到了 p 或 q（任意一个），返回找到的那个节点；如果 p、q 都不在这棵子树里，返回 null。

基于这个语义，在任意节点 root：

递归出口：root 为空返回 null；root 本身就是 p 或 q，返回 root（找到了一个，不用再往下）。
递归查左右子树，得到 left、right。
判断：
- left 和 right 都非空 → p、q 分别在两侧，root 是它们第一次汇合的点 → root 是 LCA。
- 只有一侧非空 → p、q 都在这一侧（或此刻只找到一个），把非空结果上传，让更上层去汇合。
- 都为空 → 这棵子树没有 p、q，返回 null。

三、为什么「左右都非空」就是 LCA

自底向上回溯时，第一个「左子树里有一个目标、右子树里有另一个目标」的节点，就是两条路径的汇合点。比它更深的节点不可能同时是两者祖先（否则 p、q 会在同一侧），比它更浅的节点虽然也是公共祖先但不是「最近」的。所以「左右第一次都命中」的节点恰好是 LCA。

四、二叉搜索树（BST）的 LCA 更简单

如果这棵树是 BST，可以利用有序性，不必遍历整棵树：

TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) root = root.left;   // 都比根小，去左
        else if (p.val > root.val && q.val > root.val) root = root.right; // 都比根大，去右
        else return root;   // 一个在左一个在右（或等于根），就是 LCA
    }
    return null;
}

利用 BST「左小右大」，从根往下走，第一个「p、q 分居两侧或等于当前」的节点就是 LCA，O(h)。

五、前提与易错点

上面的通用解法假设p、q 都存在于树中。若不保证存在，需要额外标记是否真找到了两个节点。
比较节点用引用相等（是不是同一个节点），一般不用值（除非题目保证值唯一）。
一个节点可以是它自己的祖先：若 p 是 q 的祖先，LCA 就是 p。上面代码 root == p || root == q 的出口正好处理了这种情况。

六、常见误区与追问

场景	推荐思路	复杂度
普通二叉树，p/q 保证存在	后序递归返回命中的节点	O(n)
普通二叉树，p/q 不保证存在	后序递归 + 计数或存在性标记	O(n)
二叉搜索树	利用有序性向左或向右走	O(h)

记忆钩子：普通二叉树的 LCA 看「左右子树是否各找到一个」；BST 的 LCA 看「两个值是否被当前节点分到两边」。

误区：LCA 一定是 p、q 之外的第三个节点。 如果 p 是 q 的祖先，那么 p 自己就是最近公共祖先。
误区：普通二叉树也可以靠节点值大小决定方向。 只有 BST 才有左小右大的有序性，普通二叉树必须遍历搜索。
误区：用值相等比较节点总是安全。 面试题常给的是节点引用，若值可能重复，必须比较节点对象本身。
误区：p 或 q 不存在时仍能直接返回命中节点。 通用模板通常假设二者存在；不保证存在时，要额外确认两个目标都被找到。
追问：为什么左右都非空时当前节点就是 LCA？ 说明 p 和 q 分别落在当前节点的左右子树，当前节点是它们第一次汇合的位置。
追问：BST 版为什么是 O(h)？ 每次根据 p、q 的值关系只走一侧，最多走树高 h 层；平衡时 O(log n)，退化时 O(n)。

七、加强记忆

LCA = 同时是 p、q 祖先且最近的节点，即两条到根路径第一次汇合处。普通二叉树用后序递归：函数语义是「子树里找到 p 或 q 就返回它」，某节点左右递归都非空说明 p、q 分居两侧、它就是 LCA；只一侧非空就上传。O(n)。BST 可利用有序性从根往下走到「p、q 分居两侧」处，O(h)。比较用引用、注意节点可为自身祖先。

简化版

详细版