手撕算法：二叉搜索树的最近公共祖先

手撕算法：二叉搜索树的最近公共祖先

引用

CSDN

1.

https://m.blog.csdn.net/weixin_43155866/article/details/136892630

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，其中每个节点的值都大于其左子树中的任何节点的值，且小于其右子树中的任何节点的值。这种性质使得二叉搜索树在查找、插入和删除操作中具有较高的效率。

在二叉搜索树中，最近公共祖先（Lowest Common Ancestor，LCA）是指两个节点在树中最近的公共祖先节点。例如，在下图中，节点4和7的最近公共祖先是6。

算法思路

由于二叉搜索树中没有相同值的节点，我们可以利用二叉搜索树的性质来寻找目标节点。具体步骤如下：

1. 从根节点开始，根据目标值与当前节点值的大小关系，递归地在左子树或右子树中查找目标节点。
2. 在查找过程中，记录从根节点到目标节点的路径。
3. 比较两个目标节点的路径，找到第一个不同的节点，该节点的前一个节点即为最近公共祖先。

代码实现

以下是使用Java实现的代码：

public class Solution {
    public int lowestCommonAncestor(TreeNode root, int p, int q) {
        // 求根节点到两个节点的路径
        ArrayList<Integer> path_p = getPath(root, p);
        ArrayList<Integer> path_q = getPath(root, q);
        int res = 0;
        // 比较两个路径，找到第一个不同的点
        for (int i = 0; i < path_p.size() && i < path_q.size(); i++) {
            int x = path_p.get(i);
            int y = path_q.get(i);
            // 最后一个相同的节点就是最近公共祖先
            if (x == y)
                res = path_p.get(i);
            else
                break;
        }
        return res;
    }

    // 求得根节点到目标节点的路径
    public ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node = root;
        // 节点值都不同，可以直接用值比较
        while (node.val != target) {
            path.add(node.val);
            // 小的在左子树
            if (target < node.val)
                node = node.left;
            // 大的在右子树
            else
                node = node.right;
        }
        path.add(node.val);
        return path;
    }
}