如何在二叉搜索树中求两个节点的最近公共祖先？

简化版

利用 BST 的有序性：如果 p 和 q 都小于当前节点，就去左子树；都大于当前节点，就去右子树；一旦当前节点的值落在 p 和 q 之间，或者等于其中一个节点，它就是最近公共祖先。

详细版

在普通二叉树里求 LCA，通常要递归左右子树，靠“左右是否分别找到目标节点”来判断。但 BST 多了一个强约束：左子树所有值小于根，右子树所有值大于根。因此从根节点开始，只要比较当前节点 cur.val 与 p.val、q.val 的大小关系，就能决定搜索方向。

如果 p.val < cur.val && q.val < cur.val，说明两个目标都在左子树，LCA 不可能是当前节点；如果 p.val > cur.val && q.val > cur.val，说明两个目标都在右子树；否则，两个节点分居当前节点两侧，或者当前节点本身就是其中一个节点，此时当前节点就是它们路径第一次分叉的位置，也就是最近公共祖先。时间复杂度 O(h)，空间复杂度迭代写法 O(1)，其中 h 是树高。

完整版教学

一、先把 LCA 的含义讲清楚

最近公共祖先不是“值最接近的节点”，而是“从根到两个目标节点的路径上，最后一个共同经过的节点”。例如在 BST [6,2,8,0,4,7,9,null,null,3,5] 中，节点 2 和 8 的路径分别是 6 -> 2、6 -> 8，共同经过的最后一个节点是 6，所以 LCA 是 6。节点 2 和 4 的路径是 6 -> 2、6 -> 2 -> 4，因为一个节点可以是自己的祖先，所以 LCA 是 2。

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

LCA(2, 8) = 6
LCA(2, 4) = 2

这道题的关键是分清“祖先关系”和“数值距离”。如果面试中把它答成“找一个数值在 p、q 中间的节点”，结论有时碰巧对，但解释不够严谨；真正的依据是从根向下走时，路径在某个节点第一次分开。

二、BST 为什么能把普通 LCA 简化成单路下降

普通二叉树没有顺序信息，目标节点可能藏在任意一侧，所以常见做法要同时递归左右子树。BST 不一样：当前节点 cur 把整棵子树切成三个区域，左边都小于 cur.val，右边都大于 cur.val，当前节点就是中间边界。只要 p 和 q 都小于 cur.val，它们不可能出现在右子树；都大于时同理。

情况	说明	下一步
`p.val < cur.val && q.val < cur.val`	两个节点都在当前节点左侧	`cur = cur.left`
`p.val > cur.val && q.val > cur.val`	两个节点都在当前节点右侧	`cur = cur.right`
其他情况	分居两侧，或当前节点命中其中一个	当前节点就是 LCA

这张表其实就是算法全部逻辑。它比普通二叉树 LCA 更快的原因，不是少写了递归，而是每一步都能排除一整棵不可能包含答案的子树。

三、用一个数字例子走完整流程

仍然看这棵树，求 LCA(3, 5)。从 6 开始，3 和 5 都小于 6，所以去左子树；到 2 时，3 和 5 都大于 2，所以去右子树；到 4 时，3 小于 4，5 大于 4，两条路径在 4 处分叉，所以答案是 4。

cur = 6: 3 < 6 且 5 < 6，去左边
cur = 2: 3 > 2 且 5 > 2，去右边
cur = 4: 3 < 4 且 5 > 4，左右分叉，返回 4

如果求 LCA(2, 5)，从 6 去左边，到 2 时 cur.val == p.val，此时直接返回 2。因为从 2 到 5 的路径会继续向右走，2 本身就是 2 和 5 的最近公共祖先。这个边界是高频追问，不能写成“必须一个在左一个在右才返回”。

四、迭代代码为什么更适合面试手写

这题天然是从根往下走一条路径，迭代写法更直观，也避免递归栈。为了让比较更统一，可以先取 low = min(p.val, q.val)、high = max(p.val, q.val)，然后判断当前节点是否落在 [low, high] 区间内。

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    int low = Math.min(p.val, q.val);
    int high = Math.max(p.val, q.val);
    TreeNode cur = root;

    while (cur != null) {
        if (cur.val > high) {
            cur = cur.left;
        } else if (cur.val < low) {
            cur = cur.right;
        } else {
            return cur;
        }
    }
    return null;
}

这里的 [low, high] 不是在说 BST 节点值可以重复，而是在描述两个目标值包出来的区间。只要 cur.val 落入这个区间，说明它不是严格在两个目标同侧之外；路径要么在它处分叉，要么它本身就是其中一个目标。

五、递归写法和普通二叉树写法的差异

递归版本也很短，但注意它递归的是一条分支，而不是左右都递归。普通二叉树 LCA 常写成“左边找、右边找、左右都有就返回 root”，那是因为没有顺序信息；BST 版只需要根据大小决定去左还是去右。

TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (p.val < root.val && q.val < root.val) return lca(root.left, p, q);
    if (p.val > root.val && q.val > root.val) return lca(root.right, p, q);
    return root;
}

复杂度公式可以写成：

时间复杂度 = O(h)
空间复杂度 = 迭代 O(1)，递归 O(h)
h = 树高；平衡 BST 中 h = log n，退化链表时 h = n

这也是回答复杂度时要补的一句话：BST 不等于一定 O(log n)，只有平衡或接近平衡时才是 O(log n)。

六、常见误区与追问

记住判断口令：同小去左，同大去右，不同或命中就返回当前节点。

误区：必须等到两个节点分别在当前节点左右两边才能返回。 如果当前节点本身就是 p 或 q，它也可能是 LCA，例如 LCA(2, 5) = 2。
误区：BST 的 LCA 要套普通二叉树 LCA 模板。 普通模板能做，但会丢掉 BST 有序性，时间通常退回到 O(n)。
误区：值更接近两个目标的节点就是 LCA。 LCA 看路径关系，不看数值距离，数值只是 BST 中帮助判断方向的工具。
追问：如果 p.val > q.val 怎么办？ 可以直接分别比较，也可以先取 low 和 high，让判断条件更稳定。
追问：复杂度为什么不是固定 O(log n)？ BST 可能退化成链表，例如按升序插入 1,2,3,4,5，树高会变成 n。
追问：如果节点不保证存在怎么办？ 需要先搜索确认 p 和 q 是否都存在，或者在找到候选 LCA 后再检查两条路径。

七、加强记忆

BST 求 LCA 的本质是“从根开始找两条搜索路径第一次分开的地方”。当前节点如果比两个目标都大，说明两条路径都还在左边；如果比两个目标都小，说明两条路径都还在右边；一旦当前节点夹在两个目标之间，或者命中其中一个目标，就说明它是两条路径最后共同经过的位置。面试时先说明和普通二叉树 LCA 的区别，再给出“同小去左、同大去右、否则返回”的迭代代码，最后补上 O(h) 与退化情况，答案就完整了。

简化版

详细版