递归
解题思路
对于二叉搜索树的最近祖先问题，其实要比普通二叉树公共祖先问题简单的多；不用使用回溯，二叉搜索树自带方向性，可以方便的从上向下查找目标区间，遇到目标区间内的节点，直接返回；
二叉搜索树性质决定了：
- 如果 p.val 和 q.val 都比 root.val 小，则 p、q 肯定在 root 的左子树，递归左子树就行；
- 如果 p.val 和 q.val 都比 root.val 大，则递归右子树就行；
这三种情况，p 和 q 的最近公共祖先都是 root：
- p 和 q 分居 root 的左、右子树；
- root 就是 p ，q 在 p 的子树中；
- root 就是 q ，p 在 q 的子树中；
复杂度
-
时间复杂度：
O(N)，其中 N 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 logN （满二叉树），最大为 N （退化为链表）； -
空间复杂度：
O(N)，最差情况下，即树退化为链表时，递归深度达到树的层数 N;
代码实现
var lowestCommonAncestor = function (root, p, q) {
// p.val 和 q.val 都比 root.val 小，则 p、q 在 root 的左子树
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
}
// p.val 和 q.val 都比 root.val 大，则 p、q 在 root 的右子树
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
}
// root 是 p 或者 q
return root;
}
迭代
解题思路
开启 while 循环，当 root 为 null 时就结束：
- 如果 p.val、q.val 都小于 root.val ，它们都在 root 的左子树，
root = root.left向左寻找；- 如果 p.val、q.val 都大于 root.val ，它们都在 root 的右子树，
root = root.right向右寻找；- 否则当前的 root 就是最近公共祖先，结束遍历；
返回 root ，即 break 时的 root 节点就是最近公共祖先；
复杂度
-
时间复杂度：
O(N)，其中 N 为二叉树节点数；每循环一轮排除一层，二叉搜索树的层数最小为 logN （满二叉树），最大为 N （退化为链表）； -
空间复杂度：
O(1)；
代码实现
var lowestCommonAncestor = function (root, p, q) {
while (root) {
if (p.val < root.val && q.val < root.val) {
// 1. 如果 p.val、q.val 都小于 root.val ，它们都在 root 的左子树，向左寻找
root = root.left;
} else if (p.val > root.val && q.val > root.val) {
// 2. 如果 p.val、q.val 都大于 root.val ，它们都在 root 的右子树，向左寻找
root = root.right;
} else {
// 3. 找到了公共祖先节点，直接退出
break;
}
}
return root;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 42. 接雨水
上一篇
评论
