求解思路
因为二叉搜索树(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;
}
|
如果觉得有帮助，欢迎点赞、关注、转发~