二叉搜索树中寻找最近公共祖先（LCA）的算法解析 | 高效解决方案

二叉搜索树（BST，Binary Search Tree）是一种特殊的二叉树，其中每个节点的左子树包含的值都小于该节点的值，右子树包含的值都大于该节点的值。在二叉搜索树中，寻找两个节点的最近公共祖先（LCA，Lowest Common Ancestor）可以利用二叉搜索树的性质来高效地解决。

问题描述

给定一个二叉搜索树和两个节点 p 和 q，找到这两个节点的最近公共祖先。

解决思路

由于二叉搜索树的性质，我们可以利用以下规则来寻找最近公共祖先：

1. 如果 p 和 q 的值都小于当前节点的值，那么它们的最近公共祖先一定在当前节点的左子树中。
2. 如果 p 和 q 的值都大于当前节点的值，那么它们的最近公共祖先一定在当前节点的右子树中。
3. 如果当前节点的值介于 p 和 q 的值之间，或者当前节点的值等于 p 或 q 的值，那么当前节点就是它们的最近公共祖先。

代码实现

以下是使用递归和迭代两种方式实现的代码示例：

递归实现

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

迭代实现

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

复杂度分析

• 时间复杂度: O(h)，其中 h 是树的高度。对于平衡的二叉搜索树，h = log(n)，其中 n 是节点数。对于最坏情况（树退化为链表），h = n。
• 空间复杂度:
  • 递归实现: O(h)，递归栈的深度取决于树的高度。
  • 迭代实现: O(1)，只使用了常数级别的额外空间。

示例

假设有如下二叉搜索树：

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

• 节点 2 和 8 的最近公共祖先是 6。
• 节点 2 和 4 的最近公共祖先是 2。
• 节点 3 和 5 的最近公共祖先是 4。

总结

利用二叉搜索树的性质，我们可以高效地找到两个节点的最近公共祖先。无论是递归还是迭代实现，时间复杂度都是 O(h)，其中 h 是树的高度。在实际应用中，迭代实现通常更为高效，因为它避免了递归调用的开销。