二叉搜索树的最近公共祖先 图解题解
两个节点什么时候开始「分道扬镳」，那个节点就是答案。
两个人从同一个城市分头出发，一个往北、一个往南——分叉口就是他们最后共享的地点。在 BST 里，利用「左小右大」从根往下走：只要 p、q 还都在同侧，就一起往那侧移；一旦一个在左、一个在右，当前节点就是它们的分叉口，也就是最近公共祖先。全程不用回头，O(h) 搞定。
这道题到底在问什么
- 输入
- BST 如图，p=3, q=12
- 输出
- LCA = 10
- 输入
- p=22, q=45
- 输出
- LCA = 30
最优解：一步一步想明白
- 3核心一句话：都小往左、都大往右，一分叉（一小一大或等于）当前即 LCA。
- 4完整的 BST。每条边左小右大。下面对三组不同的 p、q，分别从根 20 出发，看每一步该往哪走。
- 5第 1 组：要找 p = 3 和 q = 12（紫色）的最近公共祖先。先记住较小是 3、较大是 12，从根 20 开始比较。
- 6当前节点 20（橙色）。较大的 12 都还比 20 小，说明 p、q 都在左子树里 —— 往左走，去更小的一边。
- 7节点 20 处理完，往左走（绿色=已走过的路径）。下一个要比较的是 10，继续判断 p、q 在它的哪一边。
- 8当前节点 10（橙色）。这次 3 ≤ 10 ≤ 12 —— p、q 在这里第一次分道（一个往左、一个往右）。所以 10 就是最近公共祖先，停。
- 9确定了：第 1 组 p=3、q=12 的最近公共祖先是 10（绿色）。从根到这里只走了 2 步，没碰其它子树。
- 10第 1 组小结：从根沿 20 → 10 走到分叉点，最近公共祖先 = 10（绿色）。注意全程只走了一条根到节点的路径，复杂度只跟树高有关。
- 11第 2 组：要找 p = 22 和 q = 45（紫色）的最近公共祖先。先记住较小是 22、较大是 45，从根 20 开始比较。
- 12当前节点 20（橙色）。较小的 22 都还比 20 大，说明 p、q 都在右子树里 —— 往右走，去更大的一边。
- 13节点 20 处理完，往右走（绿色=已走过的路径）。下一个要比较的是 30，继续判断 p、q 在它的哪一边。
- 14当前节点 30（橙色）。这次 22 ≤ 30 ≤ 45 —— p、q 在这里第一次分道（一个往左、一个往右）。所以 30 就是最近公共祖先，停。
- 15确定了：第 2 组 p=22、q=45 的最近公共祖先是 30（绿色）。从根到这里只走了 2 步，没碰其它子树。
- 16第 2 组小结：从根沿 20 → 30 走到分叉点，最近公共祖先 = 30（绿色）。注意全程只走了一条根到节点的路径，复杂度只跟树高有关。
- 17第 3 组：要找 p = 5 和 q = 8（紫色）的最近公共祖先。先记住较小是 5、较大是 8，从根 20 开始比较。
- 18当前节点 20（橙色）。较大的 8 都还比 20 小，说明 p、q 都在左子树里 —— 往左走，去更小的一边。
- 19节点 20 处理完，往左走（绿色=已走过的路径）。下一个要比较的是 10，继续判断 p、q 在它的哪一边。
- 20当前节点 10（橙色）。较大的 8 都还比 10 小，说明 p、q 都在左子树里 —— 往左走，去更小的一边。
- 21节点 10 处理完，往左走（绿色=已走过的路径）。下一个要比较的是 5，继续判断 p、q 在它的哪一边。
- 22当前节点 5（橙色）。这次 5 ≤ 5 ≤ 8 —— p、q 在这里第一次分道（一个往左、一个往右，或一个就是它本身）。（其中 5 正好就是目标之一）所以 5 就是最近公共祖先，停。
- 23确定了：第 3 组 p=5、q=8 的最近公共祖先是 5（绿色）。从根到这里只走了 3 步，没碰其它子树。
- 24第 3 组小结：从根沿 20 → 10 → 5 走到分叉点，最近公共祖先 = 5（绿色）。注意全程只走了一条根到节点的路径，复杂度只跟树高有关。
⚠️ 容易写错的地方
✗ 错：套用普通二叉树 LCA 的「全树递归」解法
✓ 对：用 BST 有序性，从根按大小走到分叉点
普通解法 O(n) 遍历整棵树；BST 只需 O(H) 一条路径
✗ 错：分叉判断漏了「其中之一 == 当前节点」的情况
✓ 对：用 ≤ / ≥，让「等于」也落进分叉分支
p 或 q 本身就是祖先时，当前节点即 LCA，必须停
✗ 错：不先比大小，盲目左右都搜
✓ 对：都大才往右、都小才往左，一比一个方向
BST 有序，比一次就能排除半棵子树
完整代码（Python / C++ / Java）
Python
def lowestCommonAncestor(root, p, q):
node = root
while node:
if p.val > node.val and q.val > node.val:
node = node.right # 都比当前大，往右
elif p.val < node.val and q.val < node.val:
node = node.left # 都比当前小，往左
else:
return node # 分叉点 = LCAC++
TreeNode* lowestCommonAncestor(TreeNode* root,
TreeNode* p, TreeNode* q){
TreeNode* node = root;
while(node){
if(p->val > node->val && q->val > node->val)
node = node->right;
else if(p->val < node->val && q->val < node->val)
node = node->left;
else return node;
}
return nullptr;
}Java
public TreeNode lowestCommonAncestor(TreeNode root,
TreeNode p, TreeNode q){
TreeNode node = root;
while (node != null) {
if (p.val > node.val && q.val > node.val)
node = node.right; // 都比当前大，往右
else if (p.val < node.val && q.val < node.val)
node = node.left; // 都比当前小，往左
else
return node; // 分叉点 = LCA
}
return null;
}复杂度
时间
O(H)
只沿一条根到分叉点的路径，H 为树高
空间
O(1)
迭代写法只用一个指针，不递归不开栈
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉搜索树的最近公共祖先 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果是普通二叉树（不是 BST），LCA 怎么求？+
不能再靠大小走了。改用递归：从根分别在左右子树找 p、q；若 p、q 分别落在左右两边，当前节点即 LCA；若都在同一边，递归进那一边。时间 O(n)、空间 O(H)。BST 之所以能 O(H)，全靠「有序」这一额外信息。
为什么 BST 的 LCA 一定出现在「第一次分叉」处？+
LCA 要同时是 p、q 的祖先，即它的子树要同时包含 p 和 q。沿根下行时，只要 p、q 同在一侧，就还能往下走到更深的公共祖先；一旦分到两侧（或一个等于当前），再往下任何一个子树都装不下两者，所以第一次分叉的节点就是最深的公共祖先。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 二叉搜索树的最近公共祖先 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。