LeetCode 102. 层序遍历：BFS 的分层艺术

层序遍历（LeetCode 102，Medium）是 BFS 的第一课进阶：本库《岛屿数量》用过 BFS 找连通块，但那里只关心「访问过没有」；层序遍历要求按层分组输出（[[3],[9,20],[15,7]]）——从「访问」到「分层」，中间隔着一个关键技巧：按层处理循环。这个技巧的三个杀手级应用（最短路径、右视图、之字形），以及 BFS「最短性」的原理，是本篇的全部内容。

分层技巧：队列长度的快照就是本层边界

朴素 BFS：队列 + 循环弹出——访问顺序就是层序，但「层与层的边界」丢失了。分层的技巧：外层 while 循环时，先取一个快照 size = len(queue)——此刻队列里的元素恰好是「当前层的全部节点」（上一层的子节点都已入队、本层的子节点还没入队）；内层 for 循环精确弹出 size 个（本层），弹出的每个节点的子节点入队——内层结束后，队列里恰好是下一层：

from collections import deque

def level_order(root) -> list[list[int]]:
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):       # 快照：本层节点数
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)              # 本层完成
    return result

时间空间 O(n)。一个初学者陷阱：内层循环写成 while queue 或在循环内动态判断 len(queue)——入队会改变队列长度，层的边界就乱了；快照必须在处理本层之前取。这个「快照分层」技巧的直接应用：之字形遍历（LeetCode 103——偶数层反转即可，用 deque 的 appendleft 或 Python 切片 [::-1]）、每层的最大值/平均值（LeetCode 515/637——分层后对 level 做聚合，一行的事）、右视图（LeetCode 199——每层只取最后一个元素）。

杀手级应用一：无权图的最短路径——BFS 的「最短性」为什么成立

分层的最大价值在于：BFS 的层数就是「步数」——第一次到达某节点的层数，就是从起点到它的最短步数。为什么成立：BFS 按层扩展（先访问所有距离 1 的、再所有距离 2 的）——队列的单调性保证：队列中节点的距离是非降的，第一次到达节点 X 时，走的一定是最少步数（若存在更短路径，X 会在更早的层被访问）。对比 DFS：DFS 会一头扎进深处（第一次到达 X 可能绕了远路）——「无权图的最短路径用 BFS」是图论的第一铁律，而分层技巧正是「记录层数」的实现方式（起点层数 0，子节点层数 = 父节点 +1，或直接用「按层循环的轮数」计数）。应用形态：迷宫的最短出路、社交网络的 Degrees of Separation、棋盘状态的最少步数（每个状态是一个节点、每次合法移动是一条边）——只要「每步代价相同」，最短路径 = BFS 层数；代价不同的场景（带权图）则属于 Dijkstra 的世界（那是另一个故事）。

杀手级应用二与三：右视图的「层尾哲学」与树的「宽度」

右视图（LeetCode 199）：从右侧看树能看到的节点——每一层最右边的节点。分层技巧的优雅应用：内层循环里 if i == size - 1: result.append(node.val)（本层的最后一个）——或者更简单：内层结束后 result.append(level[-1])。层尾哲学的延伸：左视图取 level[0]、每层最大值取 max(level)——「分层」之后，一切「按层聚合」的需求都变成对 level 列表的一次操作——这就是分层技巧为什么是「BFS 的分层艺术」：它把队列的瞬时状态，变成了可自由加工的「层的切片」。树的宽度（LeetCode 662：最宽层的节点跨度）：分层技巧直接给出每层的跨度计算——凡是「每层」开头的问题（每层最大、每层平均、右视图、之字、最大宽度），答案都是同一套快照分层。BFS 家族的最后一块拼图是「双向 BFS」（从起点与终点同时扩展，复杂度从 O(b^d) 降到 O(b^(d/2))——本库语境里的进阶优化），它也是建立在「层」的概念上：两个 BFS 从两端逐层生长，相遇即最短——层的概念贯穿了 BFS 的一切应用。

双向 BFS 的完整思路：两端生长，相遇即答案

BFS 家族的进阶优化「双向 BFS」值得完整展开。问题背景：单词接龙（LeetCode 127）——从 beginWord 到 endWord，每次变一个字母——单向 BFS 的最坏复杂度是 O(b^d)（b 是分支因子、d 是最短距离），指数的深度项是灾难。双向 BFS 的思路：从起点与终点同时做 BFS（两个队列、两个已访问集合），每轮扩展较小的那一侧（扩张小的 frontier 成本低），任一侧的新节点出现在另一侧的已访问集合中 → 最短路径 = 两侧深度之和。为什么更快：两条 d/2 深度的搜索树的规模是 2×b^(d/2)，远小于 b^d——指数的减半是数量级的胜利。实现的纪律：「扩展小的一侧」必须真的执行（只做名义双向、每次都扩展起点侧，退化为单向）；相遇的判定在「生成新节点时」而不是「弹出时」（延迟判定会多算一层）；以及已访问集合要记录「来自哪一侧 + 深度」（相遇时两侧深度相加）。适用边界：双向 BFS 要求知道终点且图无向（或反向可走）——起点终点都明确的最短路问题适用；单向可达性检测、状态只有前进方向的场景不适用。一句话总结：知道终点在哪的时候，让搜索从两端一起生长——指数减半，是免费的速度。

队列实现的细节：deque vs list 的性能真相

BFS 的队列实现有一个 Python 特有的性能细节：为什么必须用 deque 而不是 list。list 的 popleft 问题：list.pop(0) 是 O(n) 操作（头部弹出后所有元素前移——数组的物理结构决定）——n 个节点的 BFS 用 list 做 pop(0)，总代价 O(n²)——大图上从毫秒级劣化到分钟级；deque 的 O(1) 双端：底层是双向链表块（分块数组），两端操作都是 O(1)。实测的量级：百万节点的 BFS，deque 几秒、list 的 pop(0) 版本要几分钟——不是「优化建议」，是「能不能跑完」的分界。这个细节的一般化：数据结构的「算法复杂度」与「语言实现的真实成本」可能严重背离——Python 的 list 是动态数组（尾部 O(1)），插入头部是 O(n)；某些语言的 queue 库内部是链表（head 插入 O(1)）——换一种语言，同一份「伪代码」的真实复杂度就变了。给跨语言学习者的提醒：算法的复杂度分析基于「理想操作」；工程实现要核对「这门语言的这个结构」的真实成本——本库反复强调的「实测校准直觉」，在这里的形态就是：先跑 benchmark，再选容器。

队列实现的细节：deque 与 list 的性能真相

BFS 的队列实现有一个 Python 特有的性能细节：为什么必须用 deque 而不是 list。list 的 pop 问题：list 的 pop(0) 是 O(n) 操作（头部弹出后所有元素前移——数组的物理结构决定）——n 个节点的 BFS 用 list 做 pop(0)，总代价 O(n²)——大图上从毫秒级劣化到分钟级。deque 的 O(1) 双端：底层是双向链表块（分块数组），两端操作都是 O(1)。实测的量级：百万节点的 BFS，deque 几秒、list 的 pop(0) 版本要几分钟——不是「优化建议」，是「能不能跑完」的分界。这个细节的一般化：数据结构的「算法复杂度」与「语言实现的真实成本」可能严重背离——Python 的 list 是动态数组（尾部 O(1)），插入头部是 O(n)——换一种语言，同一份伪代码的真实复杂度就变了。给跨语言学习者的提醒：算法的复杂度分析基于「理想操作」；工程实现要核对「这门语言的这个结构」的真实成本——先跑 benchmark，再选容器。

BFS 与 DFS 的「混合变体」：迭代加深搜索（IDS）

BFS 与 DFS 之间有一个混合变体值得认识：迭代加深搜索（Iterative Deepening Search, IDS）——反复调用限制深度的 DFS（先限制深度 1，没有解则限制深度 2，依次递增），直到找到解。它的巧妙之处：用 DFS 的空间实现了 BFS 的最短性——每次限制深度的 DFS 遍历会覆盖当前深度以内的所有节点，深度逐步递增保证了「浅层的解先被发现」——所以第一次找到的解必然是最短的。代价是重复计算：深度 d 的 IDS 总节点访问量约为 d 次独立 DFS 的和——但因为在树状搜索中，大部分节点在深层（底层节点占绝对多数），重复访问浅层节点的开销是可忽略的常数比例。IDS 的适用场景：搜索空间巨大（BFS 的队列存不下）、但解的深度不深（IDS 的重复可以接受）——本库语境的博弈搜索（棋类的最小最大搜索通常就是 IDS 加 alpha-beta 剪枝）。IDS 的存在证明了一个重要的算法设计原则：BFS 和 DFS 不是非此即彼——可以按需混合，取两者的长处而避两者的短处。

小结

这篇收成四条：分层技巧——外层 while 加队列长度的快照，内层 for 精确弹出本层；快照必须在处理前取（动态判长度是初学者陷阱）；BFS 的「最短性」原理——队列距离非降，首次到达即最短，「每步代价相同」的最短路径一律 BFS；分层之后，一切「按层聚合」（右视图、之字、每层最值、最大宽度）都是对 level 切片的一次操作。树的三种遍历至此集齐——DFS 前中后序（本库多篇）管「深度世界」，层序管「广度世界」——两把刷子分别刷「深」与「广」，树和图的题目就有了完整的工具箱。

参考资料

LeetCode 102. Binary Tree Level Order Traversal —— 题目与官方题解；103（之字）、199（右视图）、515（每层最大）、662（最大宽度）为家族变体
本库前篇：《LeetCode 200. 岛屿数量：DFS、BFS 与并查集三种解法》—— BFS 的第一课
双向 BFS 的优化讨论（LeetCode 127 单词接龙的进阶解法）—— 层概念的高阶应用