LeetCode 235中等二叉搜索树
二叉搜索树的最近公共祖先 图解题解
两个节点什么时候开始「分道扬镳」，那个节点就是答案。
两个人从同一个城市分头出发，一个往北、一个往南——分叉口就是他们最后共享的地点。在 BST 里，利用「左小右大」从根往下走：只要 p、q 还都在同侧，就一起往那侧移；一旦一个在左、一个在右，当前节点就是它们的分叉口，也就是最近公共祖先。全程不用回头，O(h) 搞定。
这道题到底在问什么
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科 中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（ 一个节点也可以是它自己的祖先 ）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
- root,p,q
- [6,2,8,0,4,7,9,null,null,3,5],2,8
- 输出
- 6
最优解：一步一步想明白
- 3下面 9 步动画会按主解代码推进，而不是泛泛讲题型。
- 4左子树都更小、右子树都更大在 BST 里找 LCA 有捷径：利用「左小右大」，从根开始比大小，就能直接走向 p、q 的分叉点。先标出目标 p=2、q=8。
- 5p=2 ＜ 6 想往左，q=8 ＞ 6 想往右从根 6 开始：p=2 比 6 小、在左边，q=8 比 6 大、在右边。它俩从这里分道扬镳——6 是最后一个「还把它们装在一起」的节点，也就是 LCA。
- 6分叉前同侧、分叉后分开想清楚为什么：只要 p、q 还在同一侧，它们就还共享这棵子树的根；一旦在某节点分到两边，再往下就各走各的。那个「让它们第一次分开」的节点，就是最近公共祖先。
- 7都更小→往左；都更大→往右如果换一对目标、它俩都比当前小，就一起往左走；都比当前大就一起往右；反复缩小，直到它们在某节点一左一右分开（或正好撞上其中一个），那个节点就是答案。每步砍掉一半，O(h)。
- 10记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。
⚠️ 容易写错的地方
✗ 错：当普通二叉树 LCA 做
✓ 对：利用 BST 大小关系
可以只走一条路径
✗ 错：分叉点不含等号
✓ 对：当前节点等于 p 或 q 也可返回
一个节点可以是自己的祖先
完整代码（Python / C++ / Java）
Python
class Solution:
def lowestCommonAncestor(self, root, p, q):
cur = root
while cur:
if p.val < cur.val and q.val < cur.val:
cur = cur.left
elif p.val > cur.val and q.val > cur.val:
cur = cur.right
else:
return curC++
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* cur = root;
while (cur) {
if (p->val < cur->val && q->val < cur->val) cur = cur->left;
else if (p->val > cur->val && q->val > cur->val) cur = cur->right;
else return cur;
}
return nullptr;
}
};Java
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode cur = root;
while (cur != null) {
if (p.val < cur.val && q.val < cur.val) cur = cur.left;
else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
else return cur;
}
return null;
}
}复杂度
时间复杂度
O(h)
沿树高向下
空间复杂度
O(1)
迭代写法
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉搜索树的最近公共祖先 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
BST 找 LCA 和普通二叉树(LC236)有什么不同？+
普通二叉树要后序遍历整棵树找分叉；BST 能利用「左小右大」直接顺着大小往下走，O(h) 时间、O(1) 空间，快得多。
怎么判断当前节点就是 LCA？+
p、q 都比它小就往左、都比它大就往右；只要它俩分到两侧(或有一个等于当前节点)，当前节点就是 LCA。
能做到 O(1) 空间吗？+
能。迭代版只用一个指针从根往下走、不用递归栈，空间 O(1)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。