算法学习台/算法实验台/56 天打卡/141 题/LC235
题型地图56天全屏141题

当前：LC235 · 二叉搜索树的最近公共祖先 · 首次出现于 Day 23 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC234LC236 →
92 / 141回到 Day 23 卡片141 题索引
LC235Medium二叉搜索树LCA迭代剪枝

二叉搜索树的最近公共祖先

把当前节点想成带数字路牌的岔路口：两个目标都小就一起向左，都大就一起向右；一旦开始分路，当前节点就是最低公共祖先。

题目是什么

在一棵 BST 中找到同时是 p、q 祖先且位置最低的节点。

解决什么问题

利用 BST 的有序性，不遍历无关子树，沿一条搜索路径直接定位答案。

核心结论

同小向左，同大向右；其余情况包含分岔或命中目标，直接返回当前节点。

01交互算法精讲

先说结论：这道题到底解决什么

已经站在某个 BST 节点时，怎样只凭 p、q 与当前值的大小关系，证明整棵左侧或右侧都不可能包含答案？

中心结论：同小向左，同大向右；其余情况包含分岔或命中目标，直接返回当前节点。

读完必须能回答
  1. 1.为什么 p、q 分居当前节点两侧时，当前节点就是最近公共祖先？
  2. 2.为什么 p、q 同在一侧时，可以放心丢弃另一整棵子树？
  3. 3.为什么答案可以恰好等于 p 或 q？
02交互算法精讲

完整题目与题意拆解

给定一棵二叉搜索树，以及树中的两个节点 p 和 q，返回它们的最近公共祖先。

最近公共祖先是同时覆盖 p、q 的祖先中深度最大的一个。题目采用的祖先定义允许节点是自己的祖先，因此答案可以等于 p 或 q。

  • • 所有节点值唯一，p 与 q 均存在于树中。
  • • BST 左子树值都小于当前节点，右子树值都大于当前节点。
  • • 答案不要求严格高于两个目标。
输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出：6
解释：2 在 6 左边，8 在 6 右边，6 是两条搜索路线最低的分岔点。

不要先想“遍历整棵树找两条路径”。站在当前节点，只比较 p.Val、q.Val 与 root.Val，就能判断两个目标是否仍在同一侧。

如果它们已经分居两侧，当前节点还能覆盖两者，而任何更低的单侧节点都不可能同时覆盖两者，所以当前节点就是最近公共祖先。

“其余情况”不仅包括一小一大，也包括 root==p 或 root==q；这正好覆盖“目标节点自己就是祖先”的边界。
动画 1 · 题意扫描

先看懂“最低公共路口”

观察 p=2、q=8 与根 6 的位置。先判断谁能同时覆盖两人，再判断还能不能继续向下。

Step 1/30%
主例 p=2 · q=8
6
root
2
8
0
4
7
9
3
5
root=6
看完带走：LCA 不是最高的共同祖先，而是两条目标路径最后仍重合的最低节点。
03交互算法精讲

第一层方案：暴力做法

可以分别从根搜索到 p、q，保存两条路径，再找到最后一个相同节点。这个方法正确，但需要两次搜索和 O(h) 路径空间。

也可以直接套用 LC236 的普通二叉树后序递归，时间最坏 O(n)。它忽略了 BST 的有序性，不是这题最有价值的解法。

path(root,p) = [6,2]
path(root,q) = [6,8]
最后一个公共节点 = 6
优化的关键不是更复杂的数据结构，而是把“两个目标与当前路牌的关系”一次判断清楚。
动画 2 · 暴力重复

普通树搜索为什么浪费了 BST 路牌

对照 LC236 的左右搜索：如果忽略大小关系，就会访问本可以整棵排除的分支。

Step 1/30%
常见错误
6
root
2
8
0
4
7
9
3
5
错误：只判断 p < root
看完带走：BST 的价值不是让递归更漂亮，而是用一次比较排除一整侧。

优化方向：每次比较后，搜索范围只保留左子树、右子树或立即结束。因此执行路线是一条从根向下的链，而不是整棵树的遍历。

04交互算法精讲

整体地图：先做什么，再做什么

这题先不要从递归模板出发。第一步只定义 LCA：能够同时覆盖 p、q 的祖先中，离它们最近的那个。第二步读取 BST 的有序性：左子树所有值更小，右子树所有值更大。

扫描时只维护当前 root。若 p、q 都比 root 小，答案必在左侧；若都大，答案必在右侧；其余情况表示两者在这里分开，或者 root 已经命中其中一个目标。

  • • 输入性质：这是 BST，而不是任意二叉树。
  • • 循环状态：root 是当前仍可能包含两个目标的最低候选子树根。
  • • 停止条件：分岔或命中目标时返回 root。
整套算法只有一条向下路径。真正需要证明的不是代码怎么写，而是每次丢掉的一整侧为什么一定没有答案。
05交互算法精讲

BST 路牌到底提供了什么信息

BST 在每个节点都提供一个方向路牌：比当前值小的节点只能出现在左子树，比当前值大的节点只能出现在右子树。比较 p、q 两个值，相当于同时询问两位目标会走向哪条路。

如果两者给出相同方向，当前节点还不是最低公共节点，因为更低的一侧仍可能同时覆盖它们。如果方向不同，任何更低节点都只能位于某一侧，不可能继续同时覆盖两人。

root=6, p=2, q=8  → 2<6<8，方向分开，答案是 6
root=6, p=2, q=4  → 2<6 且 4<6，答案继续去左侧
“同小向左、同大向右”是结果；背后的原因是 BST 的值域约束让另一侧不可能出现任何一个目标。
动画 3 · 核心概念

一左一右时，方向在当前节点分开

逐步比较两个目标，看到“同侧继续、分侧停止”不是口号，而是由值域决定。

Step 1/20%
检查 p
6
root
2
8
0
4
7
9
3
5
p.Val = 2 < 6
看完带走：两个目标给出不同方向时，当前节点就是最后一个还能同时覆盖两者的路口。
06交互算法精讲

如何把三种关系收敛成一个循环

每轮先同时比较 p.Val、q.Val 与 root.Val。两个严格小于才向左，两个严格大于才向右。剩余情况统一返回 root，其中既包含一左一右，也包含 root==p 或 root==q。

严格比较很重要。若把条件写成小于等于，root 命中目标时还会继续向下，反而越过正确答案。循环在 root 为空时结束只是防御性处理，题目通常保证目标存在。

  • • 两个都小：`root = root.Left`。
  • • 两个都大：`root = root.Right`。
  • • 其余情况：`return root`。

从 root 开始循环。先检查 p、q 是否都比 root 小，再检查是否都比 root 大；分别把 root 移到 Left 或 Right。

如果两种同侧条件都不成立，立即返回 root。题目保证 p、q 存在，所以正常输入会在某个节点停下。

不需要先把 p、q 按大小排序；两个并列的同侧条件对 p、q 顺序不敏感。
动画 4 · 机制构建

构建三分判断，并覆盖自身为祖先

用 p=2、q=4 观察同侧下探，再看 root 命中 p 时为什么直接返回。

Step 1/30%
同侧下探
6
root
2
8
0
4
7
9
3
5
2 < 6 && 4 < 6
看完带走：严格的同小、同大负责移动；剩余情况统一负责返回。
07交互算法精讲

核心难点：为什么分岔处不会漏掉更低答案

设 p 位于当前节点左侧、q 位于右侧。当前节点显然同时是两者祖先。若还存在一个更低的公共祖先 x，x 必须位于当前节点某一棵子树内。

但左子树中的 x 不可能成为右侧 q 的祖先，右子树中的 x 也不可能成为左侧 p 的祖先，因此更低公共祖先不存在。当前节点就是最低的那个。

同侧移动也安全：当 p、q 都小于 root 时，两者都在左子树，任何包含它们的公共祖先如果低于 root，也只能在左子树。丢弃右子树不会丢答案。

循环不变量：每轮开始时，当前 root 的子树仍然同时包含 p 和 q。移动到同侧子树后，这个条件继续成立。
正确性抓手
  • • 两目标都小于当前节点时，它们和 LCA 必然都在左子树；都大时同理在右子树。
  • • 不在同一侧时，当前节点能同时覆盖两者，而任何更低的单侧节点都不能。
  • • 命中 p 或 q 也属于停止情况，符合节点可以是自身祖先的定义。
08交互算法精讲

完整执行过程

先看 p=2、q=8 在根节点分岔，再换成 p=2、q=4 观察同侧下探。重点看每次比较为什么能安全丢弃一整侧。

  1. 1主例 p=2、q=8，从 root=6 开始；两个目标分别小于和大于 6。
  2. 2方向在 6 分开，继续向左会丢掉 8，继续向右会丢掉 2，因此立即返回 6。
  3. 3对照例 p=2、q=4，在 root=6 时两者都小，当前 root 移到左孩子 2。
  4. 4到 root=2 时命中 p；q=4 位于 2 的子树内，所以 2 同时覆盖两者且已经最低。
  5. 5整个过程只沿根到答案的一条路径移动，没有扫描被排除的子树。
动画 5 · 完整执行

两个用例串成一条完整决策轨迹

先走分岔用例，再走同侧用例；拖动时间轴比较每次 root 变化的理由。

Step 1/70%
主例 p=2 · q=8
6
root
2
8
0
4
7
9
3
5
root=6
看完带走：算法始终保留同时包含 p、q 的那棵候选子树，直到分岔或命中目标。
09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立， 再看对应代码，而不是先背模板。

动画 6 · 代码映射

三类画面状态对应三个 Go 分支

观察比较结果、root 移动和 return 高亮是否同步，重点区分严格小于与命中目标。

Step 1/40%
分岔成立
6
LCA
2
8
0
4
7
9
3
5
2 < 6 < 8
LCA = 6
看完带走：代码中的 else 同时表示“方向分开”和“当前节点命中目标”。
Step 1
先找还能同时覆盖两人的最低路口

LCA 的核心是“最低的共同覆盖点”，不是离根最近的点。

func · loop
Step 2
2 在根节点左边

BST 左子树所有节点都比当前节点小。

left-condition · right-condition
Step 3
8 在右边，两个目标从 6 分路

向左会丢掉 8，向右会丢掉 2；没有更低节点能同时覆盖两者。

left-condition · right-condition · return-root
Step 4
换成 p=2、q=4：不能在根停下

答案不可能出现在比 6 更大的右子树，保留它只会增加无效搜索。

left-condition · go-left
Step 5
root 从 6 移到 2

BST 性质已经证明被丢弃区域不可能含答案。

go-left · loop
Step 6
root 等于 p，当前节点就是答案

祖先定义允许节点包含自己；2 是同时覆盖 2 与 4 的最低节点。

left-condition · right-condition · return-root
Step 7
只比较一个目标会失去分岔信息

LCA 判断依赖两个目标相对当前节点的联合位置。

left-condition · right-condition
Step 8
这条捷径只属于 BST

普通二叉树没有值与位置的约束，LC236 必须询问左右子树并等待返回信号。

loop · left-condition · right-condition
Step 9
只沿一条根到节点的路径

没有递归栈，也没有保存路径；平衡 BST 较短，链状 BST 最坏较长。

loop · return-root · return-nil
10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法
1func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {2    for root != nil {3        if p.Val < root.Val && q.Val < root.Val {4            root = root.Left5        } else if p.Val > root.Val && q.Val > root.Val {6            root = root.Right7        } else {8            return root9        }10    }11    return nil12}
最小测试集合
// 分居两侧：答案在根
lowestCommonAncestor(root, node2, node8) // 6

// 同在左侧：必须继续下探
lowestCommonAncestor(root, node2, node4) // 2

// 目标节点本身就是祖先
lowestCommonAncestor(root, node4, node3) // 4

// 退化 BST：仍正确，时间退化为 O(n)
// 1 -> 2 -> 3, p=2, q=3  => 2
11交互算法精讲

正确性与复杂度

时间复杂度 O(h)

每轮只向下一层并丢弃另一侧，最多走过树高 h；平衡树约 O(log n)，链状树最坏 O(n)。

空间复杂度 O(1)

迭代只维护 root、p、q 三个指针，不使用递归栈或路径数组。

12交互算法精讲

最容易写错的地方

错误 1

把普通二叉树也按节点值剪枝。

错误 2

只比较 p 或 q 中的一个，无法判断是否分岔。

错误 3

认为 LCA 不能等于 p 或 q。

错误 4

把 O(h) 一概写成 O(log n)，忽略 BST 可能退化。

13交互算法精讲

最后复盘：带走逻辑链

  1. 1.BST 的有序性把全树搜索缩成单路径下探。
  2. 2.同小向左，同大向右，其余情况立即返回。
  3. 3.分岔与命中目标统一落在同一个 else 分支。
  4. 4.迁移题：LC236 普通二叉树 LCA、LC700 BST 搜索。
面试表达
  1. 1.利用 BST 左小右大的性质，从根开始同时比较 p、q。
  2. 2.两者都小就向左，都大就向右，否则说明分岔或命中目标，返回当前节点。
  3. 3.每次只保留一棵子树，所以时间 O(h)，平衡时 O(log n)、最坏 O(n)。
  4. 4.使用迭代只维护当前指针，额外空间 O(1)。