一次遍历搞定二叉搜索树的最近公共祖先

在这里插入图片描述

求解思路

因为二叉搜索树(BST)，左子树的所有节点值 < 根节点值，右子树的所有节点值 > 根节点值，利用 BST 的这个有序性，通过比较节点值来判断：

如果 root 等于 p 或 q，直接返回 root
如果 root 的值在 p 和 q 之间，说明 p 和 q 分居两侧，也是直接返回 root
如果 root 小于 p 和 q，说明两者都在右子树，向右走
如果 root 大于 p 和 q，说明两者都在左子树，向左走

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 从根节点开始向下遍历
    while (root.val != p.val && root.val != q.val) {
        // 如果 root 在 p 和 q 之间，说明找到了分叉点
        if (Math.min(p.val, q.val) < root.val && root.val < Math.max(p.val, q.val)) {
            break;
        }
        // p 和 q 都比 root 小，往左走；否则往右走
        root = root.val < Math.min(p.val, q.val) ? root.right : root.left;
    }
    return root;
}

如果觉得有帮助，欢迎点赞、关注、转发~