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

在二叉搜索树（Binary Search Tree，BST）中查找最近公共祖先（Parent-Child Ancestor，简称PCA或PAC）是指找到两个给定节点的最低共同祖先。由于BST的特性，每个节点的值大于其左子树的所有节点值，小于其右子树的所有节点值，所以查找过程类似于在一个排序序列中查找两个元素的位置。

寻找最近公共祖先的算法通常是这样的：

1. **比较目标节点**：首先比较两个目标节点的值，如果它们位于相同的分支上，则该分支的根就是它们的最近公共祖先；

2. **递归**：如果其中一个节点的值大于另一个，那么最近公共祖先在其左子树中；反之，在右子树中。然后对这个子树继续进行上述步骤，直到找到共同的祖先。

以下是伪代码形式：

def find_PCA(root, node1, node2):
    if not root or (root.val > node1.val and root.val > node2.val) or (root.val < node1.val and root.val < node2.val):
        return None
    elif root.val >= node1.val and root.val <= node2.val:
        return root
    else:
        # 根据node1或node2的大小选择左子树或右子树
        if node1.val < root.val:
            return find_PCA(root.left, node1, node2)
        else:
            return find_PCA(root.right, node1, node2)