二叉搜索树的最近公共祖先（Lowest Common Ancestor in a Binary Search Tree）

题目/知识点描述
给定一个二叉搜索树（BST）和树中的两个节点，要求找到这两个节点的最近公共祖先（LCA）。最近公共祖先定义为两个节点的最深的共同祖先节点，且这个节点可以是节点自身（如果一个节点是另一个节点的祖先）。在二叉搜索树中，利用BST的性质（左子树节点值 ≤ 根节点值 ≤ 右子树节点值）可以高效地解决这个问题，无需遍历整个树。

解题过程循序渐进讲解
我将分步骤解释如何利用BST的性质找到LCA，包括思路分析、算法步骤、示例演示和复杂度分析，确保你能透彻理解。

步骤1：理解BST性质与LCA的关系
在BST中，每个节点满足：

• 左子树的所有节点值 ≤ 当前节点值
• 右子树的所有节点值 ≥ 当前节点值
• 这个性质是递归成立的

对于两个节点p和q，它们的LCA是这样一个节点：

1. 它是p和q的公共祖先（即从根到p和q的路径上都经过该节点）。
2. 它是深度最大的公共祖先。

在BST中，LCA有一个关键特征：LCA的值一定介于p和q的值之间（包括等于p或q的值）。为什么？

• 如果当前节点值大于p和q的值，说明p和q都在左子树，LCA一定在左子树。
• 如果当前节点值小于p和q的值，说明p和q都在右子树，LCA一定在右子树。
• 否则，当前节点就是LCA（可能当前节点等于p或q，或者p和q分别位于当前节点的两侧）。

步骤2：算法思路
基于上述观察，我们可以从根节点开始递归或迭代地搜索：

1. 比较当前节点值与p、q的值。
2. 如果当前节点值 > p和q的值，则移动到左子节点。
3. 如果当前节点值 < p和q的值，则移动到右子节点。
4. 否则（当前节点值介于p和q值之间，或等于其中之一），当前节点就是LCA。

这个算法是高效的，因为每次比较都排除一半的子树（类似二分查找）。

步骤3：详细步骤与示例
假设BST如下（括号内为节点值）：

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

节点p=2，q=8。目标是找LCA。

• 从根节点6开始：
  • 比较：p=2, q=8, 当前节点值=6。
  • 6在2和8之间吗？是的（2 ≤ 6 ≤ 8），所以6就是LCA。
• 返回节点6。

另一个例子：p=0, q=5。

• 从根节点6开始：
  • 6 > 0且6 > 5，所以移动到左子节点2。
• 在节点2：
  • 2在0和5之间吗？是的（0 ≤ 2 ≤ 5），所以2是LCA。
• 返回节点2。

注意：如果p是q的祖先，则LCA就是p。例如p=2, q=4：

• 从根6开始：6 > 2且6 > 4，移到左子节点2。
• 节点2等于p，且2在2和4之间，所以2是LCA。

步骤4：递归实现
递归函数lowestCommonAncestor(root, p, q)：

• 如果root为空，返回null。
• 如果p.val < root.val且q.val < root.val，递归搜索左子树。
• 如果p.val > root.val且q.val > root.val，递归搜索右子树。
• 否则，返回root。

代码示例（Java风格）：

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

注意：这里假设p和q一定存在于树中。如果不存在，算法可能返回错误结果，但面试中通常假设存在。

步骤5：迭代实现
迭代版本更节省空间，因为不需要递归栈。思路相同：

• 从根节点开始循环。
• 根据比较决定向左或向右移动，直到找到LCA。

代码示例：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode current = root;
    while (current != null) {
        if (p.val < current.val && q.val < current.val) {
            current = current.left;
        } else if (p.val > current.val && q.val > current.val) {
            current = current.right;
        } else {
            return current;
        }
    }
    return null; // 树为空的情况
}

步骤6：复杂度分析

• 时间复杂度：O(h)，其中h是BST的高度。在平衡的BST中，h = O(log n)（n是节点数）；在最坏情况（退化为链表）中，h = O(n)。
• 空间复杂度：
  • 递归：O(h)（递归栈深度）。
  • 迭代：O(1)。

步骤7：边界情况与注意事项

1. 如果p或q不在树中，算法可能返回错误节点。可先验证节点存在性，但这通常不是必须的。
2. 如果p或q的值相等，LCA就是该节点自身（假设节点值唯一）。
3. 算法假设节点值唯一，这是BST的常见定义。

总结
利用BST的有序性，LCA问题可以高效解决，无需像普通二叉树那样存储路径或递归搜索。核心是：从根开始，根据当前节点值与p、q值的比较决定搜索方向，直到找到第一个“分叉点”或遇到p/q自身。