文章

【算法】树（二）：队列与祖先——BFS 骨架三配件、短路透传与合流

【算法】树（二）：队列与祖先——BFS 骨架三配件、短路透传与合流 摘要 树系列第二篇。上半场 BFS：LC102 层序遍历立骨架（一次"DFS 硬凑层序"的失败尝试引出一堂 slice 值语义课——子函数里的 append 回不到调用者的 slice；正解是队列 + len 快照，“先冻结规模，再动队列”），然后一个骨架吃下三个配件：LC199 右视图（i == size-1）、LC103 锯齿

发表于
作者 贾永琪
21 分钟阅读
【算法】树（二）：队列与祖先——BFS 骨架三配件、短路透传与合流

文章信息

  • 原文链接：https://jiayq.blog.csdn.net/article/details/166131512
  • 发布时间：2026-09-20 20:11:37
  • 标签：#Golang, #算法, ##开学季·九月创作之星博客挑战赛, ##树遍历, ##算法讲解

【算法】树（二）：队列与祖先——BFS 骨架三配件、短路透传与合流

摘要

树系列第二篇。上半场 BFS ：LC102 层序遍历立骨架（一次”DFS 硬凑层序”的失败尝试引出一堂 slice 值语义课——子函数里的 append 回不到调用者的 slice；正解是队列 + len 快照 ，“先冻结规模，再动队列”），然后一个骨架吃下三个配件：LC199 右视图（i == size-1）、LC103 锯齿形（一个 Reverse 引发的”每步反转”bug——2 节点的层碰巧对、4 节点的层才暴露，用例巧合家族再添一案）、LC107 自底向上（一行配件）。下半场 Boss：LC236 最近公共祖先 ——本系列思维强度最高的题：短路（命中即停，p 的子树一刀切掉）、透传（一侧有货只是传话）、合流（两侧都有货才封王）；以及最有价值的一课——我的代码迁就了我的误解 ：讲解说”短路在递归前、子树不搜”，我写代码时却把短路放在递归后，让错误的手推合法化——188 手推表”改对迁就错”的精确复现。收尾是返回值语义的升维：“语义唯一”约束的不是值是什么，是调用者怎么解释它 。

前置阅读：树（一）：递归的艺术——分解与遍历、两通道与死亡信号。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode

1. 上半场：BFS 的队列骨架

1.1 LC102：一次失败的 DFS 硬凑

层序遍历要 BFS（队列驱动），我的第一版却用 DFS 硬凑——发明了”path 收集孩子”的野路子，结果输出惨烈：root 的值整个丢失、满屏空层、层重复 。两个死因都值钱：

死因一：参数没有唯一语义。 path 收集”当前节点的孩子”、nPath 又是另一个东西——每个 slice 装着哪层、谁消费，从没定义清楚。返回值语义唯一的铁律（上一篇 543 的 62 之鉴）在参数 上同样成立。

死因二：slice 传参是 header 的值拷贝。

1
2
3
4

nPath := make([]int, 0)
dfs(nPath, ro.Left)                    // 子递归 append 到的是【nPath 的拷贝】
res = append(res, slices.Clone(nPath)) // ← nPath 还是空的！

子函数里 append 改变的是子函数自己那份 header，调用者的 nPath 纹丝不动——这就是满屏空层的直接原因。这是链表系列”重绑 vs 改对象”的 slice 版：想在递归里收集，要么用返回值回传，要么收集进闭包捕获的外层容器（res）；指望参数 slice 回传是幻觉 。（回溯系列其实做对过——path = append(path, x) 加回退，那是每层维护自己的 path，不是指望子层填父层的 slice。）

1.2 正解：队列 + len 快照

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	res := [][]int{}
	q := []*TreeNode{root}
	for len(q) > 0 {
		size := len(q)              // ★ 先冻结当前层的规模
		level := make([]int, 0, size)
		for i := 0; i < size; i++ { // 只出队 size 次——这一批就是完整一层
			n := q[0]
			q = q[1:]
			level = append(level, n.Val)
			if n.Left != nil {
				q = append(q, n.Left)
			}
			if n.Right != nil {
				q = append(q, n.Right)
			}
		}
		res = append(res, level)
	}
	return res
}

★ 是全部精髓：出队循环里孩子不断 append 进来，q 的实时长度在涨——拿实时 len 当边界，下一层的节点会被吃进当前层。先冻结快照，再动队列 。判决书（循环不变量）：任何时刻，队列里至多装着两层的节点且同层连续——上一层的残余在前、下一层的新生在后，size 快照恰好把两者切开。

顺带两笔：Go 没有内置队列，q[1:] 出队有底层数组前端无法回收的内存小坑（大流量场景用 head 下标游标）；层序里塞进 level 的顺序天然是”同层从左到右”（孩子从左到右入队、队列先进先出）——这是下面三个配件的全部依据。

1.3 三配件：一个骨架吃下一族题

LC199 右视图 ：每层最右 → if i == size-1 { res = append(res, t.Val) }。一个经典误区顺带澄清：“右视图”不是”右子树的视图” ——[1,2,3,4]（4 深在左子树）的右视图是 [1,3,4]，因为第 3 层右边没别人，4 照样入镜。i == size-1 问的是”这层最后一个出队的是谁”，不是”谁是右孩子”。

LC103 锯齿形 ：隔层反转 → 层收集完后 if levelIndex%2 == 0 { slices.Reverse(level) }。这题我栽了个藏在”碰巧对”里的 bug：Reverse 长在了内层循环里 ——每 append 一个元素就反转一次。逐步模拟 [8,9,10,11]：

1
2
3
4
5

append 8 → [8]        → rev → [8]
append 9 → [8,9]      → rev → [9,8]
append 10 → [9,8,10]  → rev → [10,8,9]
append 11 → [10,8,9,11] → rev → [11,9,8,10]   ← 期望 [11,10,9,8]，洗牌了

2 节点的层碰巧对 （长度 1 反转无效果、长度 2 恰好一次净反转），标准用例 [3,9,20,null,null,15,7] 全绿——bug 藏在 4 节点以上的宽层里。用例巧合家族再添一案：测试用例的层太窄，bug 藏在宽层里 。修复一行挪位置：反转是层级的动作 ，不是节点的动作——层收集齐了再整体掉头。

LC107 自底向上 ：slices.Reverse(res)，一行。这里要的是 Reverse 不是 Sort ——反转是顺序掉头（O(n)），排序是按值大小（O(n log n)），锯齿和倒置的需求全是前者。

三题的练习价值在”骨架复用”的肌肉：面试里 102 的骨架能吃下一整个题族（还有 429 N 叉树、637 层平均……），每题五行改动。认出”这题是那个骨架换配件”，比多背三道题的完整解法值钱 。

2. 下半场 Boss：LC236 最近公共祖先

找两个节点 p、q 的最近公共祖先（LCA）。

解法十行，判决书是树系列最深的一份：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == q || root == p {
		return root                  // ★ 短路：命中目标（或空），不往下搜
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root                  // 两侧都有货 → 合流，root 就是 LCA
	}
	if left != nil {
		return left                  // 一侧有货 → 透传
	}
	if right != nil {
		return right
	}
	return nil
}

2.1 短路：命中即停的判决书

★ 行为什么敢”不往下搜”——q 万一就藏在 p 的子树里呢？两行论证：

1
2
3
4

q 在 p 子树里   → LCA = p 自己，返回 p 恰是答案，子树里有没有 q 不影响结论
q 不在 p 子树   → 返回 p 的含义是"这边至少有一个目标"
                 → q 由另一侧的递归找到并上交，两侧非 nil 的祖先自动合流

p 的返回值同时携带两层含义 （“这边有货”的信号 + “如果 q 在我这，答案就是我”的自封候选），不需要区分——父节点只关心”有没有”，不关心”是谁”。

2.2 透传与合流：拿 LCA(6,4) 走一遍

两个目标都不是根的 case，短路不触发，靠透传和合流。树：3{5{6, 2{7,4}}, 1{0,8}}，找 LCA(6,4)：

1
2
3
4
5
6
7
8
9
10
11
12

LCA(3)：非目标 → 递归左
  LCA(5)：非目标 → 递归左
    LCA(6)：★短路（root == 6 == p）→ return 6
  5：left=6 → 递归右
    LCA(2)：非目标 → 递归左
      LCA(7)：左右 nil → return nil
    2：left=nil → 递归右
      LCA(4)：★短路（root == q）→ return 4
    2：left=nil, right=4 → 只有一侧 → 【透传】return 4    ← 2 不是合流点！
  5：left=6, right=4 → 两侧非 nil → 【合流】return 5 ★
  3：left=5，右侧 nil → 透传 return 5

反直觉点 ：4 的信号从 2 一路透传到 5 才合流——合流点不是 4 的父亲（2），而是 6 和 4 分道扬镳 的地方（5）。透传与合流的分工：一侧有货就传话，两侧都有货才封王 。

2.3 这题教我的最深一课：代码迁就了误解

我交的第二版把短路放在了递归之后 （先搜左右子树、再查 ro == p）——功能竟然也对（先搜后判时，子树里对 q 的发现被丢弃，返回 p 仍是答案），但它是误解催生的巧合正确 ：上一轮讲解明确说了”短路在递归前、p 的子树根本不进”，我手推里那些”7、4、2、6 会被搜”的错误调用——这版代码让它们成真了 。我没有修正手推去对齐理解，而是改了代码去迁就手推。

这是 188 手推表”改对迁就错”的精确复现（当年把算对的 sold 改坏去匹配算错的 hold）。遇到矛盾时，先分清哪边是对的——迁就错误的一方，错误不会消失，只会被合法化 。判据还是 122 那句话：先递归后检查的等价性，是我论证出来的吗？不是——是我碰巧站在了一个安全的位置上。

效率账也记一笔：短路版 root == p 的瞬间整棵子树不进（命中即停，最好 O(1)）；递归后检查版即使 root 就是 p 也要搜完整棵子树——渐近同是 O(n)，“发现答案就不再看一眼”是这题设计的精髓 ，丢了它等于没懂这题。

2.4 返回值语义的升维

上一篇立过铁律：“返回值必须有且只有一种语义”（543 的 62 之鉴）。但这题的返回值明明有三种身份：nil（没找到）、p 或 q（找到一个目标）、root（已合流的祖先）——铁律破了吗？

没有，是升维了。三种身份在调用者的唯一解读下等价 ：非 nil = “这棵子树里至少有一个目标，代表是这个节点”。调用者对返回值只做一种解释（“有没有货，货是谁”），不区分三种身份——语义唯一性约束的不是”值是什么”，是”调用者怎么解释它” 。这题之后，”模糊返回值 + 精确解读”成了我工具箱里的新武器（LC124 最大路径和的负值信号是同款思路）。

3. 速查表

问题判据/口诀出处
BFS 分层len 快照 ：进层前冻结 size，只出队 size 次——先冻结，再动队列LC102
slice 传参header 值拷贝，子函数的 append 回不到调用者——收集用返回值或闭包容器LC102
右视图“每层最后出队的”≠”右孩子”——i == size-1 问的是层位置不是树位置LC199
层级动作的位置反转/收集是层 的动作，放层循环末尾；放节点循环里=每步洗牌（4 节点层暴露，2 节点层碰巧对）LC103
Reverse vs Sort顺序掉头用 Reverse（O(n)），按值排大小才用 SortLC103/107
短路的判决书“不往下搜”的安全性：q 在 p 子树 → 答案就是 p；不在 → p 只是”这边有货”的信号——两种情况返回 p 都对LC236
透传 vs 合流一侧有货传话（返回那个非 nil），两侧有货封王（返回 root）；合流点=目标分道扬镳处LC236
返回值语义（升维）约束的不是”值是什么”，是”调用者怎么解释”——模糊值+精确解读是合法形态LC236
矛盾怎么办先分清哪边对；改代码迁就错误手推 = 把误解合法化 （188 复现）LC236
碰巧对的检验能讲出等价性的论证吗？讲不出 = 站在安全位置的巧合LC236

总结

上半场一个骨架三个配件，下半场一个 Boss 三份判决书。三个感想：

队列快照是 BFS 的全部秘密。 “先冻结规模，再动队列”——和滑窗的”先记收缩条件再动指针”、快慢指针的”先拉开间距再同速”是同一族动作：一切”边走边改”的结构，都要先给’当前批次’拍快照 。len 快照之后，102 到 199/103/107 只是换配件——骨架复用的肌肉，一次训练吃一个题族。

LCA 是”返回值契约”的毕业考。 543 立的规矩（语义唯一）、110 的变体（-1 信号）、236 的升维（模糊值+精确解读）——三题一条线：递归函数是一份契约，条款会越来越精妙，但”调用者怎么解释返回值必须严格对齐”这条主轴从没变过。想通 236 的”三种身份一种解读”，树形递归的返回值就再没有能吓住你的形态。

最深的一课不在题里，在我自己身上。 代码迁就误解那次——功能碰巧对、讲解全违背、误解被合法化。它提醒我：代码不说谎，但它会诚实地记录你所有的回避和误解 。头插法回避指针（树一）、野路子 DFS 回避队列（本篇 102）、短路挪位迁就错误手推（本篇 236）——三次”功能对但理解错”，每一次都是靠”讲不出为什么”暴露的。判据从第一篇用到现在，一个字没变过。

下一篇：BST 子家族（98 验证 / 230 第 K 小 / 235 BST 版 LCA / 701 插入 / 450 删除）——中序遍历的命根，”BST 的中序 = 有序序列”这一条性质吃下五道题。

参考资料

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

Golang, 算法, 开学季·九月创作之星博客挑战赛, 树遍历, 算法讲解
本文由作者按照 CC BY 4.0 进行授权