二叉搜索树的最近公共祖先

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它的每个节点的值都大于其左子树中的所有节点的值，且小于其右子树中的所有节点的值。最近公共祖先（Lowest Common Ancestor，简称LCA）是指在二叉树中，两个节点p和q的最近公共祖先节点。

对于给定的二叉搜索树，我们可以通过比较节点的值来确定最近公共祖先节点。具体步骤如下：

1. 从根节点开始遍历二叉搜索树。
2. 如果当前节点的值大于p和q的值，说明p和q都在当前节点的左子树中，因此继续遍历当前节点的左子树。
3. 如果当前节点的值小于p和q的值，说明p和q都在当前节点的右子树中，因此继续遍历当前节点的右子树。
4. 如果当前节点的值介于p和q的值之间，说明当前节点就是最近公共祖先节点。

以下是一个示例代码，演示了如何找到二叉搜索树的最近公共祖先节点：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root, p, q):
    if root.val > p.val and root.val > q.val:
        return lowestCommonAncestor(root.left, p, q)
    elif root.val < p.val and root.val < q.val:
        return lowestCommonAncestor(root.right, p, q)
    else:
        return root

# 创建一个二叉搜索树
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(8)
root.left.left = TreeNode(0)
root.left.right = TreeNode(4)
root.right.left = TreeNode(7)
root.right.right = TreeNode(9)
root.left.right.left = TreeNode(3)
root.left.right.right = TreeNode(5)

# 找到节点3和节点5的最近公共祖先
p = TreeNode(3)
q = TreeNode(5)
lca = lowestCommonAncestor(root, p, q)
print("最近公共祖先节点的值为:", lca.val)  # 输出：2