树系列第 6 篇：广度优先遍历——层序与遍历应用

欢迎来到“树系列”第 6 篇。上一篇我们以深度优先的方式把二叉树完整走了一遍：前序遍历“根左右”、中序遍历“左根右”、后序遍历“左右根”，三种遍历都建立在同一个递归骨架上，差别只在访问根的时间点。 我们还看到，深度优先就像一位一探到底的探险家，先选一条路一直走到头，走不动了再退回来换另一条路；实现它的核心工具是栈——无论是函数调用栈还是显式栈，本质上都是在“记住回头路”。今天， 我们把视角切换到另一种完全不同的走法上：广度优先遍历（Breadth-First Traversal），在二叉树语境下更常见的名字是**层序遍历（Level-Order Traversal） **。

如果说深度优先是“竖着走”的探险家，那么广度优先就是“横着扫”的扫描仪：它不急着往深处钻，而是先把当前这一层的每一个节点都看完，再一起进入下一层。这种“层层平推”的节奏，靠的不是栈， 而是一个我们在生活里天天见到的结构——队列。排队买奶茶、排队过安检、排队进地铁，都是同一个道理：先来的人先被服务，后来的人乖乖站到队尾。层序遍历和队列，几乎是天生一对。

本篇的内容路线如下：先建立“一层一层扫”的直观感受，说清楚为什么队列恰好能实现这种顺序；然后拿一棵具体的树从头到尾手算一遍，每一步都画出队列里正在排队的是谁；接着给出 JavaScript / TypeScript 的队列版代码， 并逐行解释；再解决一个进阶需求——“按层输出”，也就是如何知道一层什么时候结束；随后把 BFS 和上一篇的 DFS 放在一起做一次全面对比，包括访问顺序、空间复杂度和适用场景；之后进入本篇的重头戏——四个经典应用： 判断完全二叉树、求树的最小深度、层序序列化与反序列化、以及树的“扁平化”打印与层序号问题；最后用一张速查表把前序、中序、后序、层序四种遍历收拢在一起，并预告下一篇文章将由遍历结果反推树的结构。 如果你在查找实验室里看过树形结构的动画演示，会发现查找时高亮的那条路径，本质上就是一次“定向遍历”；而本篇要讲的，是把整棵树都扫描一遍的系统性走法。

0 先把前五篇的结论捡回来

正式出发之前，照例清点一下装备。第一，树由节点和边组成，有一个唯一根节点，除根外每个节点有且只有一个父亲；没有孩子的节点叫叶子；节点的深度是它到根经过的边数，根节点深度为 0。 第二，二叉树的每个节点最多有两个孩子，左孩子与右孩子是两个不同的位置；二叉树可以递归定义为空树，或由一个根与左右两棵子树构成。第三，完全二叉树的定义我们这一篇会反复用到： 它要求所有层都填满，除了最后一层；最后一层的节点必须从左到右连续排列，不能中间空一个再冒出节点。第 3 篇只给了定义，本篇会用队列把它变成判断算法。第四，存储：本篇代码沿用第 4 篇的链式存储， 每个节点保存值、左孩子指针、右孩子指针；但请记住，层序遍历关心的是“从节点走到它的孩子”，与底层用指针还是数组下标无关。第五，深度优先遍历：上一篇的三句话口诀“根左右”“左根右” “左右根”，以及“递归的终止条件是空子树”这个生命线，本篇会在与 BFS 的对比中反复引用。

还有一个容易混淆的术语需要提前钉死：广度优先遍历是遍历思想的名字，层序遍历是它在二叉树上的具体形态；在图上做广度优先搜索（BFS）时还要配合 visited 标记防止绕圈， 而在树上做层序遍历不需要，原因后面会专门解释。本篇先讲二叉树，最后再提一句多叉树如何扩展。

1 层序直观：一层一层扫

1.1 什么是层序遍历

深度优先讲究“先走深”，广度优先讲究“先扫平”。层序遍历的规则只有一句话：从根开始，先访问第 0 层的所有节点，再访问第 1 层的所有节点，再访问第 2 层的所有节点……每一层内部， 按照从左到右的顺序依次访问。换句话说，一个节点的访问顺序由两个条件共同决定：第一，层数（深度）小的先访问；第二，层数相同时，位置靠左的先访问。

还是用上一篇的示例树：根 A 在第 0 层；B、C 在第 1 层；D、E、F 在第 2 层；G 在第 3 层。那么层序遍历的结果就是 A、B、C、D、E、F、G。注意 C 在第 2 层没有左孩子， 但这不妨碍 F 作为 C 的右孩子继续排在 D、E 之后——层序遍历只关心节点在第几层，以及它在这一层里靠左还是靠右，并不关心它的兄弟是谁、父亲是谁。这和深度优先完全不同：深度优先里， C 要等 B 整棵子树全部走完才会轮到；而广度优先里，C 和 B 同层，B 访问完立刻就是 C，根本不需要等 D、E、G。

下面这张图把“层”用颜色和分组标了出来。你一眼就能看出层序遍历的“队形”：每一层是一排，扫描时一排一排地扫：

层序遍历为什么也叫“广度优先”？因为它在“广度”和“深度”之间永远先选广度：只要同一层还有没访问的节点，就绝不往下一层走。如果画一张访问顺序的流程图，你会看到一条“之”字形的扫描带， 从左到右扫完一层，再平移到下一层的最左边，继续从左到右：

1.2 为什么是队列：先来先服务

很多初学者拿到层序遍历的第一反应是：这个顺序用递归怎么写？答案是——层序遍历几乎不用递归写，因为递归自带的是“先深后浅”的气质，而层序遍历要求的恰恰相反。真正与层序遍历严丝合缝的数据结构是**队列（Queue） **，它的规则只有四个字：先进先出（FIFO）。先进入队列的元素，先被取出处理；后进入的元素，必须等在队尾。

我们把“排队”这个场景搬进树里。想象树的每一个节点都是一位顾客，访问节点就是“办理业务”。一开始，只有根 A 站在队伍最前面，业务员先叫 A。A 办完业务离开队伍时，它把两个孩子 B、 C 带到了队伍末尾——注意，是“办完才带”，所以 B、C 排在当前队伍最后。接下来业务员叫到队首的 B，B 办完离开，又把它的孩子 D、E 排到队尾。此时队伍里是 C、D、E：C 是 A 带来的“同层亲友” ，D、E 是 B 带来的“下一层新人”。因为 C 排在前面，所以 C 会先于 D、E 被叫到。这正是我们想要的：同一层的节点先来先办，下一层的节点即使已经入队，也必须等当前层全部办完。

这个过程的妙处在于，队列天然把“层”变成了时间差：当一个节点被访问时，它的孩子进入队尾；而队首永远站着“最早入队、还没被访问”的节点。由于入队顺序严格遵循“先访问父亲，再登记孩子” ，同一层的节点必然连续地排在队首，下一层的节点必然整体排在它们后面。所以只要不断执行“从队首取出一个节点访问，把它的孩子放入队尾”，访问顺序就自动是层序的——不需要任何额外的“当前层是第几层” 的判断。

这里值得停下来品味一下“栈 vs 队列”的对比：DFS 用栈，后进先出，所以它拿到一个新孩子后立刻转向这个孩子，一路向下；BFS 用队列，先进先出，所以它拿到一个新孩子后只是把孩子放到队伍末尾， 仍然先处理队首的“老面孔”。同样是对“拿到孩子怎么办”的回答，一个说“马上走”，一个说“先记下来，轮到了再走”，两种截然不同的遍历风格就此诞生。

1.3 树上的 BFS 为什么不需要“防回头”

在图上做广度优先搜索时，有一个绕不开的步骤：用一个 visited 集合记录已经访问过的节点，否则从某个节点出发，可能沿着环又回到已经访问过的地方，陷入死循环。为什么树上的层序遍历不需要 visited？ 因为树没有环。树里任意两个节点之间只有唯一一条路径，从根到任何一个节点的路径都是唯一的；每个节点只有一个父亲，它只可能被父亲“介绍”进队列一次，不可能被第二个节点再次入队。 因此，层序遍历天然保证每个节点恰好被访问一次，不需要额外的标记。

这一点在实现层面很有价值：队列里存的就是节点本身，不用附带“是否来过”的标记；代码里也不会有判断 visited 的分支。你可能会问：那如果某个节点的左孩子和右孩子指向同一个节点呢？ 那它就不是一棵树了——树的定义不允许一个节点有两个父亲。只要输入真是一棵树，层序遍历就不会重复，也不会漏掉。

1.4 层序遍历能解决什么问题

在深入代码之前，先建立直觉：什么任务适合层序遍历？答案是一切与“层”“深度”“最近”相关的任务。比如：找出深度最小的叶子节点；判断一棵树是否“填得整齐”（完全二叉树）；把树按层打印成漂亮的形状； 统计每一层的节点个数；在二叉树里找两个节点的最近公共祖先（当树本身按层组织的场景下）；以及序列化——把一棵树变成一行字符串，再原样变回来。这些任务都有一个共同点：它们需要“从近到远” 地扫描，或者需要知道“哪些节点在同一层”，而 DFS 要么做不到，要么做起来绕远路。

下一篇系列文章里，我们会在二叉搜索树上看到 BFS 的另一个经典用途：当树的形态不保证平衡时，用 BFS 从根向外找，可以更快地定位“离根最近”的某种节点。现在只需要记住一句话：DFS 适合“把整条路径看完” ，BFS 适合“从近到远地扩散”。

1.5 从二叉树到多叉树，再到图

层序思想并不局限于二叉树。多叉树的每个节点有任意多个孩子， 层序遍历的规则不变：先访问根，再从左到右依次访问它的所有孩子…… 只要把“左孩子入队、右孩子入队”换成“把所有孩子依次入队”即可。 代码甚至比二叉树版本更简单：

function bfsMulti(root: MultiNode | null): number[] {
  if (root === null) return [];
  const result: number[] = [];
  const queue: MultiNode[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node.val);
    for (const child of node.children) {
      queue.push(child);
    }
  }

  return result;
}

这里的 MultiNode 用 children: MultiNode[] 保存孩子列表。 整段代码的核心与二叉树版本一字不差：取出队头、访问、把孩子全部入队。 这也说明了一个重要的学习规律：层序遍历的骨架与节点有几个孩子无关， 只与“先来先服务”的队列纪律有关。

再往远处走一步。树是特殊的图；在图上做广度优先搜索（BFS）时， 规则同样是从起点出发逐层扩散，但多了一个必须的动作——用 visited 标记 已经访问过的节点。原因在 1.3 节说过：图可能有环，也可能从多个方向 到达同一个节点；没有 visited，算法会在环里打转， 或者把同一个节点重复入队多次。树的层序之所以“轻”， 正是因为树没有环、每个节点只有一个父亲，队列顺序天然唯一。 所以，当你以后从树的层序转到图的 BFS 时，请记住一句话： 队列的骨架完全一样，只是多了一个 visited。

2 算法手算：把一棵树完整走一遍

直觉建立之后，动手算。理论再漂亮，如果不亲手推一遍队列的变化，写代码时还是会卡在“什么时候入队、什么时候出队”上。这一节我们沿用上一篇的示例树，从第一行代码开始之前，先把每一步的队列内容、 出队节点、入队节点全部写出来。请准备好纸笔，或者干脆跟着文章在脑子里“运行”一遍。

2.1 示例树与书写约定

示例树还是那棵 A–G 树：根是 A，A 的左孩子是 B、右孩子是 C；B 的左孩子是 D、右孩子是 E；C 没有左孩子，右孩子是 F；E 有左孩子 G，没有右孩子。整棵树有 7 个节点、 3 片叶子（D、F、G），高度为 3。为了手算方便，我们把层序“摊开”写一遍：第 0 层是 A；第 1 层是 B、C；第 2 层是 D、E、F；第 3 层是 G。

手算时我们约定：队列写成一条从左到右的队伍，最左边是队头（下一次将被取出），最右边是队尾（新来的排在这里）。比如“队列：[B, C]”表示 B 在队头、C 在队尾，下一次出队的是 B。 访问序列用一条独立的记录，每出队一个节点，就把它的值追加到序列末尾。

再强调一个贯穿全程的细节：空孩子不入队。当队列弹出 B 时，B 有左右两个孩子 D、E，都入队；当弹出 C 时，C 没有左孩子，那就什么都不入，只有右孩子 F 入队。空孩子不是节点， 不参与访问，所以在普通层序遍历里直接跳过。这个“跳过空孩子”的规则，到 6.3 节序列化时会反过来用——那时空孩子要显式记成 null，才能把树的形状完整保存。

2.2 七步走完全程

现在开始。初始时刻，队列里只有根 A，访问序列为空。整个过程的每一步都遵循同一条纪律：队头出队并访问；把它的非空孩子按“先左后右”的顺序入队。这条纪律只有两句话，但请务必记住， 它就是后面所有代码的原型。

第 1 步：队头 A 出队，访问 A，访问序列变成“A”。A 有左孩子 B、右孩子 C，按先左后右入队，队列变成 [B, C]。

第 2 步：队头 B 出队，访问 B，访问序列变成“A, B”。B 有左孩子 D、右孩子 E，入队后队列变成 [C, D, E]。注意此刻队伍里 C 排在 D、E 前面——C 是第 1 层的人， D、E 是第 2 层的人，第 1 层还没扫完，第 2 层只能等着。

第 3 步：队头 C 出队，访问 C，访问序列变成“A, B, C”。C 没有左孩子，只有右孩子 F，所以只把 F 入队，队列变成 [D, E, F]。到这里，第 1 层已经全部访问完毕， 而队首恰好是 D——第 2 层的最左边一个节点。这不是巧合：当一层访问完时，下一层的节点已经全部在队里按从左到右排好了。

第 4 步：队头 D 出队，访问 D，访问序列变成“A, B, C, D”。D 是叶子，没有孩子，队列变成 [E, F]。

第 5 步：队头 E 出队，访问 E，访问序列变成“A, B, C, D, E”。E 有左孩子 G，把 G 入队，队列变成 [F, G]。

第 6 步：队头 F 出队，访问 F，访问序列变成“A, B, C, D, E, F”。F 是叶子，队列变成 [G]。

第 7 步：队头 G 出队，访问 G，访问序列变成“A, B, C, D, E, F, G”。G 是叶子，队列变成空。队列为空，意味着没有等待访问的节点了，遍历结束。

最终结果：A、B、C、D、E、F、G，和 1.1 节预言的一模一样。

下面这张示意图把每一步的队列状态连成一条时间线，你可以从左往右看，就像看一场“排队办理业务”的动画：

再把同样的过程整理成一张表，方便你逐行核对。表里“操作”一栏描述这一步做什么，“出队”是离开队伍的节点，“入队”是新进队伍的节点，“访问序列”是到目前为止的结果：

步骤	操作	出队	入队	访问序列	队列
初始	根入队	—	A	空	[A]
1	弹出队头	A	B、C	A	[B, C]
2	弹出队头	B	D、E	A, B	[C, D, E]
3	弹出队头	C	F	A, B, C	[D, E, F]
4	弹出队头	D	无	A, B, C, D	[E, F]
5	弹出队头	E	G	A, B, C, D, E	[F, G]
6	弹出队头	F	无	A, B, C, D, E, F	[G]
7	弹出队头	G	无	A, B, C, D, E, F, G	空

检查这张表，你会发现三个规律。第一，访问序列按层分组：A 一组，B、C 一组，D、E、F 一组，G 一组，组与组之间的界线清晰。第二，每一组内部的顺序就是从左到右： 第 2 层是 D、E、F，恰好对应它们在树中的左右位置。第三，下一层的顺序在入队时就定好了：D、E、F 之所以按这个顺序进队，是因为 B 先把自己的两个孩子 D、E 放进队尾， 然后 C 才把 F 放进队尾；先入队的先被访问，顺序就自然保持了。

2.3 为什么“刚好”是层序：不变量视角

如果只看上面七步，你可能觉得“哦，好像挺顺的”，但说不清为什么一定正确。这里给一个更严谨的视角，叫循环不变量：在处理过程的任意一个时刻，队列里保存的节点，恰好是按层序排列的“待办清单” ——队首是当前层还没访问的最左节点，队尾是已经发现但还没轮到的更深层节点；并且当前层剩余节点全部排在下一层已发现节点之前。为什么这个性质一直成立？因为每次出队一个当前层节点，它的孩子都属于下一层， 被放进队尾，排在所有当前层剩余节点之后；等到当前层节点全部出队，队首自然变成下一层的最左节点。这个不变量从初始状态（队列只有根，根就是第 0 层的唯一节点）成立，经过每一步操作仍然成立， 所以结束时访问序列必然是层序。

很多教材直接给结论“队列实现层序遍历”，但从不解释为什么。现在你可以这样向别人证明：队列的 FIFO 顺序，就是“发现节点的先后顺序”；而树里发现节点的先后，天然按层展开——父亲先于孩子， 同层节点按入队顺序排列。把两者一拼，层序遍历就自动发生了。 这不是魔法，而是两个简单规则的叠加。

2.4 队列里最多有多少个节点

手算时还有一个值得留意的问题：队列会不会越来越大？在我们的例子里，队列最大时是 3 个节点（第 2 步之后的 [C, D, E] 和第 3 步之后的 [D, E, F]）。这不是偶然。 一棵二叉树里，队列长度大致等于“某一层节点的数量”再加上“下一层已入队的一部分”，最坏情况下可能接近树的宽度——也就是某一层最多有多少个节点。这个观察到第 5 章会变成严谨的空间复杂度分析： BFS 的空间开销由树的宽度决定，而 DFS 的空间开销由树的高度决定。先把“宽”这个字记在心里，第 5 节我们会把它和“高”做一次正面对决。

2.5 三个边界手算：空树、单节点、只有右孩子

前面的大树走得很顺，但边界情况才是区分“会写”和“写对”的分水岭。 把三个极端形状各算一遍，队列机制的边界就彻底清楚了。

空树：root 为 null。初始化队列为空，主循环一次都不执行， 直接返回空数组。这就是第 3 章第一行判空的意义： 没有根，就没有第一次入队，一切动作都无从谈起。

单节点树：只有根 A。队列初始为 [A]；弹出 A，访问 A； A 没有孩子，什么都不入队；队列变空，循环结束，结果为 [A]。 当树只有一个节点时，层序、前序、中序、后序全部退化成 [A]—— 所有遍历都变成“访问一次”，这个平凡情形是检验代码的试金石： 任何遍历实现都必须在单节点树上输出一个元素， 而不是空数组或者两个元素。

只有右孩子的链：根 X 只有右孩子 Y，Y 只有右孩子 Z。 逐行走一遍：

步骤	出队	入队	访问序列	队列
初始	—	X	空	[X]
1	X	Y	X	[Y]
2	Y	Z	X, Y	[Z]
3	Z	无	X, Y, Z	空

结果是 X、Y、Z。有意思的是，前序遍历的结果也是 X、Y、Z。 在一条链上，没有分支可供深度优先与广度优先做出不同的选择， 两种遍历结果自然重合。这也从侧面说明： DFS 和 BFS 的差别，只会在树真正“分叉”时显现； 链状结构对两者而言只是同一条路，怎么走都是它。

2.6 顺带算一笔账：一层最多有多少个节点

手算时我们关心队列有多大，这背后其实是一个简单的数学问题： 二叉树的一层最多能有多少个节点？结论是：第 k 层最多有 2 的 k 次方个节点 （根在第 0 层，是 2 的 0 次方，也就是 1 个）。每一层的节点数 至多翻一倍：第 0 层 1 个，第 1 层 2 个，第 2 层 4 个， 第 3 层 8 个……这个规律从“每个节点最多生两个孩子”直接推出： 一层有 m 个节点，下一层最多就是 2m 个。

层号	最多节点数
0	1
1	2
2	4
3	8
k	2 的 k 次方

把前 k 层全部加起来，得到 1 + 2 + 4 + …… + 2 的 k 次方 = 2 的 (k+1) 次方减 1。所以一棵有 n 个节点的二叉树， 如果每一层都尽量填满，它的高度大约是 log2(n+1) 减 1， 通常记作 O(log n)。反过来，n 个节点的“最胖”树， 最后一层大约有 n/2 个节点——这正是 BFS 队列最满的时候。 这两笔账合在一起，就是第 5 节复杂度对比的数学底子： 高度对数增长、宽度指数增长，是二叉树最核心的几何性质。

3 代码实现：队列版层序遍历

手算练熟了，代码只是把手算过程“翻译”一遍。这一节先给出一个最简单的 TypeScript 实现，再逐行解释； 然后讨论一个很多初学者踩过的坑——用数组的 shift 方法模拟队列的性能问题；最后给出一个更接近真实队列的写法。

3.1 节点类型

继续沿用第 5 篇的链式存储定义。每个节点保存自己的值、左孩子指针、右孩子指针； 左右孩子都可能是空，用 null 表示：

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};

如果你使用 JavaScript，没有类型声明也没关系，把代码里的 TreeNode 去掉即可； 下面所有代码的核心逻辑与语言无关。

3.2 最直观的队列版

function levelOrder(root: TreeNode | null): number[] {
  if (root === null) return [];       // 空树：没有节点可访问

  const result: number[] = [];        // 访问序列
  const queue: TreeNode[] = [root];   // 队列，先把根放进去

  while (queue.length > 0) {          // 只要还有人排队，就继续
    const node = queue.shift()!;      // 1. 队头出队
    result.push(node.val);            // 2. 访问它

    if (node.left !== null) {         // 3. 左孩子入队
      queue.push(node.left);
    }
    if (node.right !== null) {        // 4. 右孩子入队
      queue.push(node.right);
    }
  }

  return result;                      // 全部访问完毕
}

逐行解释。第一行 if (root === null) return [] 处理空树：没有根，就没有任何节点可访问，直接返回空数组。 这是层序遍历的“生命线”，和 DFS 递归里的空子树终止条件地位相同。

const result = [] 是访问记录，每出队一个节点就追加它的值。 const queue = [root] 是队列的初始状态——手算时第一步“根入队”就对应这一行。

while (queue.length > 0) 是主循环。队列非空，说明还有节点等待访问；队列空了，说明整棵树扫完。 循环体里四件事：出队、访问、左孩子入队、右孩子入队。注意顺序：先取出队头 queue.shift()，再访问； 访问之后才把孩子放进队尾。如果把入队放在出队之前，孩子会插到队首的位置，顺序立刻乱掉。 shift() 返回的可能为 undefined，TypeScript 里用 ! 告诉编译器“这里一定非空”—— 因为循环条件已经保证队列非空。

两个 if 是“空孩子不入队”的代码化：左孩子为 null 就不入，右孩子为 null 就不入。 有些教材写成 if (node.left) queue.push(node.left)，在节点值不为 0 时等价； 但为了语义严谨，这里显式写 !== null，避免 val 为 0 或空字符串时误判。

这个版本和手算过程一一对应：手算第 1 步“A 出队、B、C 入队”对应循环第一次迭代； 第 7 步“G 出队”对应最后一次迭代。跑一遍示例树，返回的数组就是 [1, 2, 3, 4, 5, 6, 7]（如果把 A–G 换成数字）。

3.3 一个性能陷阱：shift 不是免费的

上面的代码虽然正确，但有一个隐患：JavaScript 数组的 shift() 会把所有剩余元素往前挪一位， 时间复杂度是 O(n)。也就是说，在 n 个节点的树上，虽然每个节点只出队一次， 但每次出队都可能触发一次整体搬移，总代价可能达到 O(n²)。对于小树无伤大雅， 但在 LeetCode 风格的大数据测试里可能超时，在真实业务里会拖慢响应。

更贴近“队列”语义的做法是：用下标记录队头，而不是真的把元素从数组前面删除。 数组仍然负责存节点，但我们维护一个 head 指针，出队只是“head 加一”，入队还是 push。 当 head 追上数组长度时，说明队列空了：

function levelOrder(root: TreeNode | null): number[] {
  if (root === null) return [];

  const result: number[] = [];
  const queue: TreeNode[] = [root];
  let head = 0;                       // 队头下标

  while (head < queue.length) {       // 队头还没越过队尾，说明还有人
    const node = queue[head];         // 读取队头
    head++;                           // 队头前进，等价于出队
    result.push(node.val);

    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
  }

  return result;
}

这个版本里，“出队”变成了两行：先 queue[head] 读，再 head++。 数组本身只增不减，所以每个节点仍然恰好被处理一次，总时间是 O(n)。 代价是数组会一直占着已处理节点的位置，空间上略显浪费；实际使用时可以定期把已消费的部分截断， 或者直接用双端队列结构。不过对算法学习而言，head 指针版本已经足够， 而且它引出了一个重要的视角：队列不一定非要用“删除头部”实现，“头部下标移动”同样是队列。 后面第 4 节按层输出时，这个视角会再次派上用场。

3.4 复杂度分析

时间复杂度：每个节点恰好入队一次、出队一次、被访问一次，所以是 O(n)，其中 n 是节点总数。 对二叉树的每条边，最多被检查两次（父亲访问时检查左、右），也在 O(n) 范围内。

空间复杂度：主要开销是队列。最坏情况是一棵“满二叉树”的最后一层， 队列里几乎同时装着最后一层的一半以上节点，数量级是 O(n/2) = O(n)。 更精确的说法是 O(w)，w 是树的最大宽度。注意这个 w 与树的形状强相关： 在一条链状的树上，w = 1，BFS 的空间只是 O(1)；在一棵非常“胖”的树上，w 可能接近 n/2。 第 5 节会把它和 DFS 的 O(h) 放在一起对比。

3.5 常见错误清单

写层序遍历最容易犯的错误有三个。第一，忘了判空：root 为 null 时， queue = [root] 会得到一个“有一个空元素”的队列，循环里访问 node.val 直接报错。 第二，用错顺序：先入队孩子再取出队头，或者把访问写在孩子入队之后，都会打乱顺序； 记住固定顺序“取出、访问、左入、右入”。第三，把左右孩子入队的顺序写反： 层序遍历要求同一层从左到右，所以必须先左后右；如果先入右孩子，第 2 层的顺序就变成从右到左了。 另外，如果使用 shift 版本，还要警惕在循环里边 shift 边用索引遍历数组——那会漏掉节点。 遇到顺序类的 bug，把队列打印出来，和 2.2 节的表逐行对照，几乎立刻能找到问题。

3.6 队列的工程实现：从数组到链表

到目前为止，我们用数组当队列。数组队列在算法题里够用， 但工程上有两个问题：shift 的 O(n) 搬移，以及 head 指针版本中 “已消费位置”的空间积累。真实系统里的队列实现通常有这几种：

• 链表队列：每个元素是一个节点，持有数据和指向下一个元素的指针； 入队在尾部追加，出队移动头指针。入队、出队都是 O(1)， 没有搬移，也没有“空洞”积累。代价是每个元素多存一个指针， 节点分散在内存里，缓存不友好；
• 环形数组：一块固定大小的数组加头、尾两个下标， 头尾越过末尾时回绕到开头。入队、出队 O(1)，空间固定， 适合已知最大规模的场景，比如操作系统里的任务队列；
• 语言内置队列：JavaScript 没有内置的 Queue 类； Python 的 collections.deque、Java 的 ArrayDeque、 C++ 的 std::queue 都是开箱即用的选择。

那么在算法题里用哪种？我的建议分两档。刚入门时， 用 queue.shift() 版本：它和手算过程一一对应，最不容易写错； 熟悉之后，切换到 head 指针版本，避免大输入时超时。 如果面试官追问性能，能说出“shift 是 O(n)， 用下标模拟可以做到 O(1) 出队”就已经达标。 链表队列属于数据结构本身的知识，不需要为了层序遍历现场手写—— 除非面试题明确要求“不使用内置队列”实现一个队列， 那又是另一个考点了。

还有一个细节值得知道：在 head 指针版本里，数组会一直保存 已经处理过的节点，直到整个遍历结束才一起释放。 如果树的节点非常大、遍历时间又长，这个“只增不减”的数组 会带来额外的内存压力。工程上常见的处理是：每当 head 超过 某个阈值（比如数组长度的一半），就用 slice 把已消费部分切掉， 重置 head 为 0。这样既保留了 O(1) 出队，又控制了内存增长。 当然，对算法题而言这些优化都不必要，知道原理即可。

3.7 调试技巧：让队列可见

初学层序遍历时，最大的敌人是“脑子里跑不动代码”。 一个非常有效的调试技巧是：在循环里把队列的内容打印出来， 让每一步都可见。比如在 while 循环的入口加一行：

console.log(
  "队列：",
  queue.slice(head).map((n) => n.val)
);

配合“出队节点”和“访问序列”的打印， 你就能得到一份和 2.2 节手算表一模一样的运行日志：

队列： [A]
出队 A，入队 B、C；队列： [B, C]
出队 B，入队 D、E；队列： [C, D, E]
出队 C，入队 F；队列： [D, E, F]
出队 D；队列： [E, F]
出队 E，入队 G；队列： [F, G]
出队 F；队列： [G]
出队 G；队列： []

把运行日志和手算表逐行对照，如果哪一行对不上， bug 就锁定在那一步。这个技巧看似笨拙， 却是所有调试方法里最直接的一种： 不要猜，让数据结构自己说话。 等你能熟练写出这个日志，说明队列的每一步 都已经长在直觉里了，之后再去掉调试代码即可。

4 “按层输出”：如何知道一层何时结束

4.1 需求：从一维结果到二维结果

第 3 章的 levelOrder 返回的是一个一维数组 [A, B, C, D, E, F, G]。 但很多场景需要知道“哪些节点属于同一层”，比如把树按层打印成多行、统计每层的节点数、 或者按层给节点编号。这时我们希望得到的是二维数组： [[A], [B, C], [D, E, F], [G]]，每一行代表一层。

问题来了：基本的队列版层序遍历里，出队顺序虽然是层序的， 但代码本身并不“知道”某一层什么时候结束。它只知道“队列空了就停止”。 我们必须想办法在遍历过程中标记层的边界，这正是本节的题目： 如何知道当前层已经结束？

4.2 方案一：记录每层节点数（双循环写法）

最常用的办法来自一个漂亮的不变量：当外循环开始处理某一层时，队列里恰好装着这一层的全部节点。 为什么？回顾 2.3 节：上一层的节点全部出队后，队首正好是当前层的最左节点； 而在处理上一层的过程中，当前层的节点已经全部按从左到右的顺序进入队尾。 所以外循环开始时，队列的长度（head 到队尾之间的元素个数）就是当前层的节点数。

利用这个不变量，我们可以在进入每一层之前，先把当前层的节点数记下来， 然后用一个内层循环恰好处理这么多个节点；内层循环过程中新入队的节点， 自然是下一层的人，留给下一次外循环处理。这就是“双循环写法”：

function levelOrderByLevel(root: TreeNode | null): number[][] {
  if (root === null) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let head = 0;

  while (head < queue.length) {            // 还有节点，说明还有层
    const levelSize = queue.length - head; // 当前层节点数
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {  // 只处理当前层
      const node = queue[head];            // 队头出队
      head++;
      level.push(node.val);

      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    result.push(level);                    // 一层处理完，收工
  }

  return result;
}

逐行解释。levelSize = queue.length - head 是关键中的关键： 它必须在内层循环之前计算。如果把它写进循环条件里写成 i < queue.length，那么每处理一个节点，队列就会因为入队而变长， 内层循环会停不下来，把下一层的节点也一并处理掉，整个分层就乱了。 先“拍照”记下本层人数，再按这个数字处理，是这套写法的灵魂。

内层循环里干的事和普通层序遍历一模一样：取出队头、记录值、左孩子入队、右孩子入队。 区别只在于，这个循环有明确的次数上限，不会“顺手”把下一层也处理掉。 一层处理完，result.push(level) 把这一层的结果收进二维数组， 然后回到外循环，继续处理下一层。

用示例树验证一遍。外循环第一次开始时，队列是 [A]，levelSize = 1， 内循环只处理 A，入队 B、C，得到 [A]。第二次外循环开始时，队列是 [B, C]， levelSize = 2，内循环处理 B（入队 D、E）和 C（入队 F），得到 [B, C]。 第三次外循环开始时，队列是 [D, E, F]，levelSize = 3， 内循环处理 D、E（入队 G）、F，得到 [D, E, F]。 第四次外循环开始时，队列是 [G]，levelSize = 1，得到 [G]。 最终结果 [[A], [B, C], [D, E, F], [G]]，完全正确。

下面这张图把“层边界”标了出来：每一层开始时记下 size， 处理完 size 个节点，这一层就收工，队列里剩下的正好是下一层：

4.3 方案二：层尾哨兵

另一种思路是在队列里放一个“哨兵”节点标记层的结束：每层处理完， 往队尾放一个特殊值，遇到哨兵就知道该换层了。 这种写法在面试中也出现过，但实现起来要小心两个细节： 第一，空树时不要往队列里放哨兵，否则会死循环； 第二，处理完一层发现队列里已经没有真实节点时，不能再往队尾追加新的哨兵， 否则又会出现“光杆哨兵”的无限循环。相比之下，双循环写法不需要哨兵， 也不会遇到这些边界问题，所以更推荐。哨兵写法真正的价值在于直观： 它把“层结束”这件事变成了队列里的一个可见标记， 适合用来理解层的概念，而不是用来写生产代码。

4.4 还有第三种思路：带着层号一起入队

既然普通队列只存节点，我们也可以让队列里存“节点 + 层号”的组合。 根节点层号是 0，孩子节点的层号是父亲层号加一。 这样每取出一个元素，就知道它属于第几层，把值放进对应层的数组即可。 这种写法能精确知道每个节点的层号，但需要为每个节点额外存一个数字， 空间上多花一点，代码上也比双循环啰嗦。它的用途在于：当任务本身就要求“层号” （比如给节点编号、统计每一层、按层间隔打印）时，层号跟着节点走， 逻辑最直白。

4.5 双循环写法能顺手解决哪些问题

一旦掌握了“每层节点数”这个抓手，很多问题就变成填空题：

• 统计每层节点数：把 level.length 收集起来，或者直接记录最大的 levelSize，就是树的最大宽度；
• 层序号问题：给 result 数组的每一行加一个层号，就得到“节点在第几层”的完整答案；
• 锯齿遍历：处理完一层后，按层号奇偶决定正序还是倒序收集，就得到之字形遍历；
• 按层打印：每一层一行，直接输出 result 的每个子数组；
• 自底向上的层序：把 result 整体反转，就是“从叶子层到根层”的顺序。

这些变体都不需要改变队列的核心逻辑，只需要在“层边界”处做文章。 所以请把双循环写法练到闭眼能写：它是 BFS 应用题的万能脚手架。

4.6 两个高频变体：锯齿遍历与自底向上

双循环写法最精彩的证明，是它稍微改几行就能解决两个经典变体。

锯齿遍历（之字形）：要求奇数层从左到右、偶数层从右到左。 做法是照常分层，然后根据层号决定要不要反转这一层的结果：

function zigzagLevelOrder(root: TreeNode | null): number[][] {
  if (root === null) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  let head = 0;
  let levelNo = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const level: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head];
      head++;
      level.push(node.val);
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    if (levelNo % 2 === 1) level.reverse();
    result.push(level);
    levelNo++;
  }

  return result;
}

核心只有一行：if (levelNo % 2 === 1) level.reverse();。 队列里的顺序永远是层序（从左到右），但输出时按层号奇偶反转， 就得到之字形。用示例树验证：第 0 层 [A]，第 1 层 [B, C] 不反转， 第 2 层 [D, E, F] 反转成 [F, E, D]，第 3 层 [G] 反转后还是 [G]。

自底向上的层序：先按正常顺序分层，最后把整个结果数组反转：

const bottomUp = levelOrderByLevel(root).reverse();

就这么简单。每一层的内部顺序不受影响，只是层的先后顺序反过来。 比如示例树自底向上的结果是 [[G], [D, E, F], [B, C], [A]]。

这两个变体在面试中出现频率极高，它们共同证明了一个道理： BFS 负责把“层”切出来；层与层怎么排列、层内怎么排列， 都可以在分层之后自由加工。切层是 BFS 的职责， 排列是业务规则，两者解耦，代码才清晰。

4.7 层号与下标的数学关系

既然聊到层号和层内位置，不妨把 2.6 节的数学用上。 在一棵按层序编号（从 0 开始）的树里， 第 L 层的节点占据的下标范围是：从 2 的 L 次方减 1， 到 2 的 (L+1) 次方减 2。比如第 0 层是下标 0， 第 1 层是下标 1、2，第 2 层是下标 3、4、5、6。 这串数字和第 2.6 节的表格完全对得上： 每一层的起点，恰好是前面所有层的节点总数。

于是“层内第几个位置”可以反推：节点下标 index 减去 本层起点（2 的 L 次方减 1），就是它在层内的序号。 反过来，知道层号和层内序号，也能直接算出下标。 这套换算在两类场景里特别有用：一是数组存储的树 （第 4 篇、6.7 节），二是需要“按形状打印”的可视化任务 （6.4 节）：先算出每个节点的下标，再根据层内序号 决定水平缩进，树的轮廓就出来了。

这里想强调的不是公式本身，而是一个思考习惯： 层序不仅是一种访问顺序，还是一种坐标系统。 层号是纵坐标，层内序号是横坐标； 有了坐标系，很多“看起来要画图”的问题， 就变成了纯数学计算。

5 与 DFS 对比：走法、空间与适用场景

第 5 篇已经把深度优先的三种遍历讲透了，本篇又把广度优先摆上台面。 是时候让两位主角正面交锋：访问顺序有什么不同？空间复杂度谁高谁低？ 什么任务该选谁？这一节用一张对比表和几组极限例子，把这些一次性说清。

5.1 访问顺序：路径优先还是层优先

同样面对示例树，DFS 的前序遍历结果是 A、B、D、E、G、C、F， BFS 的层序遍历结果是 A、B、C、D、E、F、G。差别一目了然：

• DFS 沿着一条路径走到底：A 到 B 到 D，然后回到 B 再去 E、G， 直到 B 的整棵子树走完，才轮到 A 的右孩子 C；
• BFS 按层平推：A 访问完立刻轮到同层的 B、C，然后才轮到第 2 层的 D、E、F， 最后是第 3 层的 G。

这个差别的本质是“先处理谁”的优先级不同。DFS 认为“深”优先： 只要还有向下的路，就继续往下；BFS 认为“近”优先： 只要同一层还有人没处理，就绝不往下走。你可以把 DFS 想象成 在迷宫里走一条线，把 BFS 想象成水波扩散——从根开始， 一圈一圈向外推开，每一圈就是一个层。

5.2 空间复杂度：BFS 看宽度，DFS 看高度

两种遍历的时间复杂度都是 O(n)，因为每个节点都恰好访问一次。 真正拉开差距的是空间复杂度，而它们的“空间账本”完全不同。

DFS 的空间看高度。递归版 DFS 的空间主要花在函数调用栈上： 栈里同时压着从根到当前节点的一条路径，路径最长不超过树的高度 h， 所以空间是 O(h)。迭代版用显式栈，同理。h 的取值与树的形状强相关： 一棵退化成链的树，h = n，DFS 需要 O(n) 的空间； 一棵完美平衡的二叉树，h = log2(n)，DFS 只需要 O(log n)。

BFS 的空间看宽度。队列里同时装着“当前层剩余节点 + 下一层已入队节点”， 数量级由树的最大宽度 w 决定，所以空间是 O(w)。最坏情况是一棵满二叉树： 最后一层有约 n/2 个节点，BFS 的空间接近 O(n)； 而一条链状树每一层只有一个节点，w = 1，BFS 的空间只是 O(1)。

把两个维度放到一起，就会看到一组非常戏剧性的对比：

树的形状	高度 h	最大宽度 w	DFS 空间	BFS 空间
链状（歪树）	n	1	O(n)	O(1)
满二叉树	log2(n)	n/2	O(log n)	O(n)
一般二叉树	不确定	不确定	O(h)	O(w)

这张表说明了一个反直觉的事实：DFS 和 BFS 没有谁绝对省空间。 在又高又瘦的树上，BFS 更省；在又矮又胖的树上，DFS 更省。 实际选择时，先估计一下你的树“胖”还是“瘦”，再决定用谁。

下面这张图把两者的“记忆负担”画了出来：BFS 需要同时记住一整层的节点， DFS 只需要记住从根到当前节点的一条路径：

5.3 适用场景对比表

空间只是一方面，更重要的是任务本身需要什么样的顺序。 下面这张表总结了常见场景的推荐选择，以及理由：

任务类型	推荐	理由
找离根最近的节点 / 目标在浅层	BFS	逐层向外，第一个命中就是最近
求树的最小深度	BFS	遇到的第一个叶子必然深度最小
判断完全二叉树	BFS	层序天然适合检查“空缺是否出现在最后”
按层处理、统计每层	BFS	双循环直接给出层边界
找从根到某节点的路径	DFS	路径是一条链，DFS 天然沿着链走
判断两棵树是否相同	DFS	结构比较按递归骨架最自然
表达式树求值	DFS（后序）	必须先算子树再算根
二叉搜索树有序输出	DFS（中序）	中序天然有序
序列化 / 反序列化	两者皆可	前序或层序都能存，选你熟悉的
图的连通分量、迷宫寻路	DFS / BFS 皆可	看具体是“找路径”还是“找最近”

5.4 一句话决策法则

如果任务问“离根最近”“第几层”“一层一层”，优先 BFS； 如果任务问“从根到某处的路径”“子树的结构关系”“先算孩子再算根”， 优先 DFS。还有一个实用技巧：当你不确定时， 可以想一想“如果目标节点在很深的地方，我能接受一层一层扫过去吗”。 目标深且树窄，DFS 可能更快；目标浅且树宽，BFS 几乎总是更优。 两者都不是银弹，但把这两种“走法”都装进脑子里， 你就能在遇到新问题时先选对工具，再写代码。

5.5 工程视角：递归深度与提前终止

除了理论上的空间复杂度，还有两个工程因素会影响遍历选择。

第一，递归深度限制。DFS 的递归版在“歪树”（高度接近 n）上 会递归 n 层，而语言运行时通常有最大调用栈限制 （浏览器里常见的是几千层到几万层），超过就抛栈溢出异常。 BFS 用循环实现，没有递归深度问题。所以当树可能很深时， 要么用 DFS 的迭代栈版本，要么干脆用 BFS； 这也是很多生产环境的代码规范禁止深递归的原因。

第二，提前终止能力。BFS 在“找最近”类问题上可以提前返回 （6.2 节的最小深度就是例子）；DFS 在“找路径”类问题上， 找到第一条路径往往也能提前返回。提前终止意味着实际运行时间 常常远小于最坏情况 O(n)，在数据量大时收益非常可观。 写代码时，把提前返回的条件放在循环里最显眼的位置， 既是性能优化，也是让意图更清晰的表达。

补充一个容易误会的点：虽然 DFS 的 O(h) 在平衡树上很漂亮， 但“平衡”这个前提并不总是成立。真实世界的树， 比如从无序数据直接插入的二叉搜索树，可能退化成链； 此时 DFS 的 O(n) 空间是实打实的风险，而 BFS 反而只需要 O(1)。 所以“BFS 一定更费空间”的印象，只在满二叉树等“宽树”上成立。 正确的姿势永远是：先估计树的形状，再选遍历方式。

5.6 两个极端例子，把账算明白

空谈复杂度容易晕，拿具体数字算一遍就清楚了。

例子一：一千个节点的链状树。树的高度约 1000，宽度是 1。 DFS 递归版需要约 1000 层调用栈，很多运行时的默认限制 就在几千层，已经逼近危险区；迭代栈版本需要同时保存 最长约 1000 个节点。BFS 的队列里永远只有 1 个节点， 空间是常数级别。结论：歪树上，BFS 的空间完胜。

例子二：一千零二十三个节点的满二叉树（10 层）。 高度是 10，最后一层有 512 个节点。DFS 的栈最多约 10 层， 空间非常小；BFS 扫到最后一层时，队列里约有 256 到 512 个节点， 空间是 BFS 自己的最坏情况。结论：胖树上，DFS 的空间完胜。

树的形状	节点数	DFS 空间	BFS 空间
链状树	1000	约 1000（栈）	约 1
满二叉树	1023	约 10	约 512

这两个例子值得反复看，因为它们纠正了一个常见偏见： “DFS 一定省空间”和“BFS 一定费空间”都不对。 正确的问题是：你的树高不高？宽不宽？ 回答了这个问题，遍历选择就不是玄学，而是算术。

6 BFS 的经典应用

掌握了层序遍历的骨架之后，我们来看看它真正发光的地方。 这一节讲四个经典问题：判断完全二叉树、求最小深度、层序序列化与反序列化、 以及树的“扁平化”打印与层序号问题。它们共享同一个套路—— 用队列维持层序，然后在“访问节点”这一步做文章。

6.1 判断完全二叉树

先复习第 3 篇的定义：一棵二叉树是完全二叉树，当且仅当 除最后一层外，每一层都被填满；最后一层的节点从左到右连续排列， 中间不能出现空缺。换句话说，把整棵树按层序“摆”成一行， 完全二叉树的节点应该像数组一样紧密地排在最前面， 空位只能出现在序列的最后。

这个“按层序摆成一行”的视角，正好是 BFS 的主场。 判断方法非常朴素：按层序遍历这棵树，但这次把空孩子也当成占位符入队； 一旦遇到第一个空位（null），它之后就不能再出现任何非空节点。

function isCompleteTree(root: TreeNode | null): boolean {
  if (root === null) return true;   // 空树按定义是“满”的

  const queue: (TreeNode | null)[] = [root];
  let seenNull = false;             // 是否已经见过空位

  while (queue.length > 0) {
    const node = queue.shift()!;    // 取队头，可能是 null

    if (node === null) {
      seenNull = true;              // 记录：出现第一个空位
      continue;                     // 空位没有孩子，无需入队
    }

    if (seenNull) return false;     // 空位之后还有节点，不合格

    queue.push(node.left);          // 空孩子也要入队占位！
    queue.push(node.right);
  }

  return true;                      // 全程没有“空位之后冒节点”
}

这个算法和普通层序遍历只有一个关键区别： 空孩子不再被跳过，而是以 null 的身份入队。 为什么要入队 null？因为完全二叉树要求“紧密排列”， 判断的不是“哪些节点存在”，而是“空位出现在哪里”。 把 null 放进队列，等于在层序序列里保留了所有“本来应该有节点 但实际没有”的位置，让空位成为序列中可见的元素。

手动走一遍。假设一棵树：1 有左孩子 2、右孩子 3； 2 只有左孩子 4；3 只有右孩子 5。 队列按层序依次弹出：1、2、3、4、null、null、5。 前四个节点都正常；接着出现两个 null，标志 seenNull 变成 true； 可这时队列里居然还有一个 5！按照规则，空位之后不能再有节点， 所以这棵树不是完全二叉树。确实，第 2 层缺了两个位置 （2 的右孩子、3 的左孩子），第 3 层却冒出一个 5， 节点没有从左到右连续排列，不合格。

再看一棵完全二叉树：1 有孩子 2、3；2 有孩子 4、5； 3 只有左孩子 6。层序序列是 1、2、3、4、5、6、null、null、null。 第一个 null 出现之后，后面全是 null，没有一个非空节点， 所以返回 true。这两棵树的对比画在下面：

时间复杂度 O(n)：每个真实节点入队一次，每个 null 占位也最多入队一次， 总共 O(n) 个元素；空间 O(w)，w 是最大宽度。 这个算法是面试高频题，因为它把“完全”这个结构性定义， 翻译成了一行几乎不费脑子的判断：seenNull 之后不能再见非空。

补充一个更数学的等价做法：如果把完全二叉树的节点按层序编号 （根是 1，左孩子是 2i，右孩子是 2i+1），那么一棵 n 个节点的树是 完全二叉树，当且仅当所有节点的编号都不超过 n。 这个做法可以不用队列，但需要为每个节点记录编号， 实现上比队列法多一个“编号越界检查”，两种都值得了解。

6.2 树的最小深度：第一个叶子

树的最小深度，是从根到最近一片叶子的距离。 沿用本篇的约定，深度按边数计算：根到第一层节点是 1 条边， 所以只有根一棵节点时，最小深度是 0； 如果按“节点数”计算（LeetCode 常见），根本身算深度 1， 两种口径只差一个 1，思路完全一样。

用 DFS 求最小深度也能做，但必须遍历完整棵树： 因为你不知道哪条路最短，只能把所有叶子都看一遍。 用 BFS 就聪明得多：层序遍历天然从近到远， 遇到的第一片叶子，一定就是离根最近的叶子， 找到它就可以立刻返回，后面的层都不用扫了。

function minDepth(root: TreeNode | null): number {
  if (root === null) return 0;

  const queue: TreeNode[] = [root];
  let head = 0;
  let depth = 0;                    // 当前层的深度（边数）

  while (head < queue.length) {
    depth++;                        // 进入新的一层
    const levelSize = queue.length - head;

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head];
      head++;

      if (node.left === null && node.right === null) {
        return depth;               // 第一片叶子就是答案
      }

      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
  }

  return depth;                     // 理论上到不了这里（空树已提前返回）
}

代码就是第 4 章“按层输出”的变形：外循环每进一层，depth 加一； 内循环检查这一层的每一个节点，一旦发现叶子，立刻返回当前深度。 因为 BFS 保证层号从小到大，所以第一个命中的叶子必然深度最小。

用示例树验证：第 0 层只有 A，不是叶子；第 1 层是 B、C， 都不是叶子；第 2 层是 D、E、F，其中 D 和 F 是叶子， 内循环从左到右先碰到 D，立即返回深度 2。 而 D 确实是离根最近的叶子之一（G 在第 3 层，更远）。

最坏情况下（比如一棵“歪”树，叶子全在很深的位置）， BFS 也要扫完整棵树，时间是 O(n)；但平均情况下， 只要叶子出现在较浅的层，BFS 就能提前退出，常常比 DFS 快很多。 空间上同样是 O(w)。这个“找第一个叶子”的思路， 还可以推广到“找离根最近的满足某条件的节点”， 是 BFS 在树上最典型的应用模式。

6.3 序列化与反序列化：层序版，null 占位

把一棵树变成字符串存进文件、数据库或消息队列，之后还能原样还原， 这个过程叫序列化与反序列化。第 5 篇提过前序序列化； 这一节看层序版本，它的好处是直观：树长什么样， 序列就几乎长什么样。

层序序列化的核心思想，我们在 6.1 节已经见过：null 占位。 把整棵树按层序摊开，空孩子用 null 标记，就得到一棵树的 “完整快照”。例如树 1 → 2、3，2 → 4，3 → 5， 序列化为 [1, 2, 3, 4, null, null, 5]。 有了 null，序列里每个位置是“谁”都清清楚楚， 反序列化时才能把形状还原，而不是只还原节点值。

class TreeNode {
  constructor(
    public val: number,
    public left: TreeNode | null = null,
    public right: TreeNode | null = null
  ) {}
}

function serialize(root: TreeNode | null): string {
  if (root === null) return "[]";

  const vals: (number | null)[] = [];
  const queue: (TreeNode | null)[] = [root];

  while (queue.length > 0) {
    const node = queue.shift()!;
    if (node === null) {
      vals.push(null);              // 空位写 null
    } else {
      vals.push(node.val);          // 真实节点写值
      queue.push(node.left);        // 孩子都入队，包括 null
      queue.push(node.right);
    }
  }

  while (vals.length > 0 && vals[vals.length - 1] === null) {
    vals.pop();                     // 去掉结尾多余的 null
  }
  return JSON.stringify(vals);
}

serialize 的逻辑和普通层序遍历几乎一样，只有一处不同： 空孩子不再跳过，而是以 null 的身份入队、以 null 的身份写进序列。 注意一个细节：弹出 null 时，不把它的“孩子”入队—— null 不是节点，没有孩子。正因为如此，即使队列里会积累很多 null， 每个 null 也只是写一个值就结束，不会造成死循环。

序列末尾可能拖着一串 null（最后一层的空孩子）， 它们不影响树的形状，所以最后一步把它们去掉， 让序列更紧凑。你也可以选择不去尾，两种格式反序列化时都能正确处理。

反序列化是序列化的逆过程：从左到右读序列， 用队列维护“等待分配孩子的节点”。根先创建并入队； 之后每弹出一个父亲，就从序列里取下一个值当左孩子、 再取一个值当右孩子；非 null 的孩子创建节点并入队， 因为它自己也迟早要有孩子：

function deserialize(data: string): TreeNode | null {
  const vals = JSON.parse(data) as (number | null)[];
  if (vals.length === 0) return null;

  const root = new TreeNode(vals[0]!);
  const queue: TreeNode[] = [root];
  let i = 1;                         // 序列游标

  while (i < vals.length) {
    const parent = queue.shift()!;   // 等待分配孩子的节点

    if (vals[i] !== null) {          // 左孩子
      parent.left = new TreeNode(vals[i]!);
      queue.push(parent.left);
    }
    i++;

    if (i < vals.length && vals[i] !== null) {  // 右孩子
      parent.right = new TreeNode(vals[i]!);
      queue.push(parent.right);
    }
    i++;
  }

  return root;
}

这个反序列化器的正确性依赖于一个关键事实： 序列化时，每个非空节点都“按层序”把自己的两个孩子写进了序列。 所以读序列时，队列里等待分配孩子的父亲们，恰好也是按层序排列的； 父亲们一个一个领取自己的两个孩子，顺序永远不会乱。 用示例序列 [1, 2, 3, 4, null, null, 5] 走一遍： 根 1 入队；弹出 1，取 2 当左孩子、3 当右孩子，2、3 入队； 弹出 2，取 4 当左孩子、null 当右孩子（不创建），4 入队； 弹出 3，取 null 当左孩子、5 当右孩子，5 入队； 弹出 4，序列已经读完，结束。树完美还原。

下面这张图把“树 ↔ 层序序列”的对应关系画出来， 每一个下标都能在树上找到自己的位置：

序列化与反序列化的时间都是 O(n)，空间 O(n)。 和前序序列化相比，层序版的优点是不需要递归深度， 不会在“歪树”上撑爆调用栈；缺点是序列里 null 较多， 字符串更长。两者各有拥趸，面试时能写清楚一种并说明取舍即可。

6.4 树的“扁平化”打印与层序号问题

日常调试时，我们经常想把一棵树“摊平”打印出来。 最朴素的做法就是按层输出：每一行是一层，节点之间用空格分隔。 这正是第 4 章双循环写法的直接应用：

function printFlat(root: TreeNode | null): void {
  if (root === null) return;

  const queue: TreeNode[] = [root];
  let head = 0;
  let depth = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const parts: string[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head];
      head++;
      parts.push(String(node.val));
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    console.log(`第 ${depth} 层：${parts.join("  ")}`);
    depth++;
  }
}

示例树会打印成三行：

第 0 层：A
第 1 层：B  C
第 2 层：D  E  F
第 3 层：G

这个输出已经回答了“层序号问题”的一半：每个节点属于第几层。 如果还想知道“它在这一层里的第几个位置”， 在把节点写进 parts 时记录下标即可。这种“层号 + 层内位置” 的二维坐标，是描述树形布局的基础。

更进一步的“扁平化”是给整棵树编号，让它和数组存储对上号。 第 4 篇讲过：若根的下标是 1，则节点 i 的左孩子下标是 2i， 右孩子是 2i+1；若从 0 开始，则左孩子是 2i+1、右孩子是 2i+2。 层序遍历恰好以这个顺序访问节点，所以你可以边遍历边编号， 得到每个节点在“数组版二叉树”里的下标。

为什么这有用？举三个例子。第一，判断完全二叉树： 用数组下标编号后，只要所有节点下标都不超过节点总数 n， 树就是完全的——这和 6.1 节是同一个事实的两种表述。 第二，按形状打印：知道节点下标后，可以根据层号和层内位置 计算打印时的缩进，把树“画”成金字塔形，而不是简单的逐行列表。 第三，堆的层序：下一系列的堆（完全二叉树的数组实现） 正是靠这套下标公式在父子之间跳转的，层序遍历就是堆的“自然序”。

最后提醒一点：如果只是调试，逐层打印完全够用； 但如果你要做“可视化”，光有层号还不够， 还需要知道每个节点相对根的水平偏移量——这是二叉树绘图的话题， 本篇点到为止。你可以在查找实验室里 看到树形结构动画是如何把层序和坐标结合起来的， 那正是“层序号问题”的一个完整落地。

6.5 应用：二叉树的右视图

“二叉树的右视图”是层序应用的又一个经典：从右侧看一棵二叉树， 能看到的节点，恰好是每一层最右边的那个节点。 BFS 解法几乎是白送的——先按层分组，然后取每一组的最后一个元素：

function rightSideView(root: TreeNode | null): number[] {
  if (root === null) return [];
  const result: number[] = [];
  const queue: TreeNode[] = [root];
  let head = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;
    let lastVal = 0;

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head];
      head++;
      lastVal = node.val;              // 每层最后一个就是最右
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    result.push(lastVal);
  }

  return result;
}

lastVal 在内层循环里被不断更新，循环结束时， 它恰好保存这一层最后一个节点的值——也就是从右侧能看到的值。 用示例树验证：第 0 层最后是 A，第 1 层最后是 C， 第 2 层最后是 F，第 3 层最后是 G，右视图是 [A, C, F, G]。 从树的形状看完全合理：A 挡住 B 和 D，C 挡住 E 和 G 的一部分， F 在右侧最外，G 是最后一层最右边的节点。

类似的题目还有“左视图”（每层取最左），以及 “每一层最中间的节点”“每一层最左侧的叶子”等变体。 它们共同展示了 BFS 的一个特长：按层处理时， 层内位置信息几乎是免费的——只要在双循环里多记一个变量。

6.6 应用：二叉树的最大宽度

如果只统计每层有几个真实节点，那是最大“节点数”； LeetCode 662 问的是最大“宽度”，定义更严格： 一层里最左节点与最右节点之间的位置数，包括中间的空位。 比如 6.1 节那棵非完全树，第 2 层只有 4 和 5， 但 4 在位置 4、5 在位置 6，中间隔着空位， 所以这一层的宽度是 3，而不是节点数 2。

怎么用 BFS 算宽度？给节点编号。沿用数组存储的下标体系： 根是 1，节点 i 的左孩子是 2i，右孩子是 2i+1。 层序遍历时，队列里同时保存节点和它的编号； 每层结束时，用“最右编号 - 最左编号 + 1”更新最大宽度：

function widthOfBinaryTree(root: TreeNode | null): number {
  if (root === null) return 0;

  let maxWidth = 0;
  const queue: { node: TreeNode; index: number }[] = [
    { node: root, index: 1 },
  ];
  let head = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;
    const firstIndex = queue[head].index;   // 本层最左编号

    for (let i = 0; i < levelSize; i++) {
      const { node, index } = queue[head];
      head++;

      if (node.left !== null) {
        queue.push({ node: node.left, index: index * 2 });
      }
      if (node.right !== null) {
        queue.push({ node: node.right, index: index * 2 + 1 });
      }

      if (i === levelSize - 1) {
        maxWidth = Math.max(maxWidth, index - firstIndex + 1);
      }
    }
  }

  return maxWidth;
}

编号技巧在第 4 篇的数组存储和本篇 6.4 节都出现过， 在这里它是算法的核心：不编号，就无法知道空位占了多少宽度。 注意编号会随深度指数增长，树很深时可能超出整数安全范围； 工程上有“相对编号”的优化（每层把最左节点归一化为 1）， 本篇只提一句，不展开。这个例子再次说明： BFS 给的不仅是一个访问顺序，还是一套天然的层内坐标， 很多难题之所以用 BFS 简单，正是因为坐标系统是白送的。

6.7 应用：从层序数组直接建树

有时输入本身就是层序数组（比如 6.3 节序列化的结果， 或者用数组存储的堆），需要从数组直接建出链式树。 6.3 的反序列化器已经做过这件事；这里再看一种更简洁的写法—— 利用数组存储的下标公式，连队列都不用：

function buildFromLevelArray(
  vals: (number | null)[]
): TreeNode | null {
  if (vals.length === 0 || vals[0] === null) return null;

  const nodes: (TreeNode | null)[] = vals.map((v) =>
    v === null ? null : new TreeNode(v)
  );

  for (let i = 0; i < nodes.length; i++) {
    if (nodes[i] === null) continue;

    const left = 2 * i + 1;      // 0 基下标：左孩子
    const right = 2 * i + 2;     // 0 基下标：右孩子
    if (left < nodes.length) nodes[i].left = nodes[left];
    if (right < nodes.length) nodes[i].right = nodes[right];
  }

  return nodes[0];
}

原理来自第 4 篇的数组存储：按层序把节点放进数组后， 下标 i 的节点的左孩子在 2i+1、右孩子在 2i+2。 第一步先把数组里的每个值变成节点（null 保持 null）， 第二步逐个给非空节点挂孩子，越界就说明没有那个孩子。 两步各 O(n)，总时间 O(n)，空间 O(n)。

用 [1, null, 2] 验证：节点 1 的下标 0，左孩子下标 1 是 null， 右孩子下标 2 是节点 2，所以 1 只有右孩子 2， 与数组表达的树完全一致。这种写法把“树 ↔ 数组”两个视角 焊在了一起：层序遍历可以把树压成数组， 下标公式可以把数组还原成树。堆、线段树等结构 都是在这个转换上盖楼房的。

6.8 应用：每层的最大值与平均值

如果任务变成“求每一层的最大值”或“每一层的平均值”， 双循环写法依然只是加几行的事。核心思想不变： 进入一层时初始化一个变量，内层循环里更新它， 层结束时把结果记下来。

function levelMax(root: TreeNode | null): number[] {
  if (root === null) return [];

  const result: number[] = [];
  const queue: TreeNode[] = [root];
  let head = 0;

  while (head < queue.length) {
    const levelSize = queue.length - head;
    let maxVal = -Infinity;

    for (let i = 0; i < levelSize; i++) {
      const node = queue[head];
      head++;
      maxVal = Math.max(maxVal, node.val);
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }

    result.push(maxVal);
  }

  return result;
}

把 maxVal 换成 sum 并除以 levelSize，就是每层平均值； 换成数组收集每个值，就是完整的按层输出。可以看到， 从“按层输出”到“每层最大值”，代码的差异只有三四行。 这就是为什么我们说双循环是 BFS 应用题的万能脚手架： 层边界一旦掌握，剩下的都是业务逻辑。

6.9 层序与堆：一个重要的桥梁

如果你听说过“堆”这种数据结构，一定见过一句话： 堆是一棵完全二叉树，通常用数组存储。这里“用数组存储” 的数组顺序，正是层序遍历的顺序：数组下标 0 是根， 下标 1、2 是第一层，下标 3、4、5、6 是第二层…… 第 4 篇讲过的下标公式（左孩子 2i+1、右孩子 2i+2） 就是在给层序序列里的每个位置“上户口”。

为什么堆偏偏要完全二叉树？因为完全二叉树的节点 从层序序列的开头连续排列，中间没有空缺， 数组里就不会浪费位置；而“父子下标公式”让堆可以在 不存指针的情况下，用纯数学在父子之间跳转。 向上调整（上浮）就是“从 i 走到 (i-1)/2”， 向下调整（下沉）就是“从 i 走到 2i+1 或 2i+2”。 这些操作全是下标运算，而生成这个下标的底层顺序， 就是本篇的层序遍历。

所以你可以把层序遍历看作三样东西的公共语言： 链式树、数组存储、堆。学会了用队列扫层序， 你就同时理解了数组版的树为什么长这样； 将来学堆排序、优先队列、线段树时， “层序 = 数组顺序”这个等式会反复出现。 本篇不展开堆的实现，但请记住这个桥梁—— 树系列后面讲到堆的时候，你会感谢现在记住的层序。

7 四种遍历总结：一张表收拢全部走法

走到这里，二叉树的四种主流遍历已经全部登场： 前序、中序、后序（深度优先）和层序（广度优先）。 这一节把它们放在同一张表里做最终总结， 并且回答一个经常被问到的问题：它们之间到底是什么关系？

7.1 四种遍历总表

遍历	访问顺序	口诀	递归	迭代	典型用途
前序	根、左子树、右子树	根左右	自然	栈	复制树、序列化
中序	左子树、根、右子树	左根右	自然	栈 + 指针	二叉搜索树有序输出
后序	左子树、右子树、根	左右根	自然	双栈或反转	删除树、表达式求值
层序	逐层从左到右	层层扫	不自然	队列	按层处理、最短路径

7.2 记忆法：根的位置决定名字

第 5 篇给过一句口诀：“根的位置决定名字”。 前序遍历把根放在最前面访问，所以叫“前”；中序遍历把根放在 左子树和右子树中间，所以叫“中”；后序遍历把根放到最后，所以叫“后”。 三个名字都不是随便起的，而是对“什么时候访问根”的诚实描述。 层序不在这条口诀里，因为它的排序规则不是“根在第几位”， 而是“谁在更浅的层”。给层序配一句自己的口诀：“层层扫，队里绕”—— 一层一层从左到右扫，实现上绕不开队列。

7.3 实现骨架：递归三兄弟与队列一人

前序、中序、后序的递归写法共享同一个骨架：

function dfs(node: TreeNode | null, visit: (n: TreeNode) => void) {
  if (node === null) return;
  // 在这里 visit(node) → 前序
  dfs(node.left, visit);
  // 在这里 visit(node) → 中序
  dfs(node.right, visit);
  // 在这里 visit(node) → 后序
}

三次 visit 的位置，正好对应节点被“经过”的三个时刻： 刚到达时、从左子树回来时、从右子树回来时。 三种深度优先遍历，不过是把“访问”这个动作 安放在三个不同时刻而已。迭代版本也一样：用栈模拟这个骨架， 只是需要自己控制压栈顺序（后序稍麻烦一点，常见技巧是 先按“根右左”入栈再反转，或者给节点打标记）。

层序则是完全不同的骨架：没有“递归到子树”的动作， 只有“取出、访问、孩子入队”的循环。它的递归写法不是不能写 （可以带着层号递归），但既不直观也不省事， 所以实际中几乎总是用队列。记住这个分工： 前中后是“递归三兄弟”，层序是“队列独行侠”。

7.4 一个统一视角：路径与层

如果一定要给四种遍历找一个统一的坐标系， 可以说它们都在回答同一个问题：“下一个访问谁？” DFS 的答案是：沿着当前路径，先走最深的分支； BFS 的答案是：按发现顺序，先走最早入队的节点。 前者维护的是“一条路径”，后者维护的是“一层候选”。 理解到这个层面，四种遍历就不再是四个孤立的算法， 而是同一棵树上两种调度策略的四种具体姿势。

7.5 从遍历结果能知道什么

每种遍历都会泄露树的一部分信息。知道“泄露了什么”， 是理解很多高级题（包括下一章的重建问题）的基础。

• 前序：第一个元素必然是根；任意子树的节点在前序里连续成块；
• 中序：根把整个序列分成左右两半，左右子树的划分信息最直接；
• 后序：最后一个元素必然是根；子树节点同样连续成块；
• 层序：按层分组，天然给出深度信息；第一个元素是根。

那么，哪些遍历组合能唯一重建一棵二叉树？ 下面这张表是本章与下一章之间的桥梁：

拥有的信息	能否唯一重建	关键原因
前序 + 中序	能	前序定根，中序分左右
后序 + 中序	能	后序定根，中序分左右
前序 + 后序	通常不能	只有一个孩子的节点，方向不明
层序 + 中序	能	层序定根的先后，中序分左右
只有前序 / 后序 / 层序	不能	缺少左右划分信息
一种遍历 + null 占位	能	空位完整记录了形状

这张表值得反复看：它解释了为什么序列化必须记录 null （6.3 节），也预告了为什么“重建树”偏偏要前序 + 中序 而不是前序 + 后序。遍历不只是“走一遍”， 更是把树的结构编码成序列的过程； 理解了每种编码丢失了什么、保留了什么， 你才算真正吃透了遍历。

8 预告：由遍历结果重建一棵树

8.1 问题长什么样

有一个经典问题经常出现在面试和竞赛里：给定一棵二叉树的中序遍历 和前序遍历结果，能否把这棵树原样重建出来？ 比如前序是 A、B、D、E、G、C、F，中序是 D、B、G、E、A、C、F， 要求还原原来的树。答案是可以——前提是节点值互不重复， 并且我们知道用的是哪两种遍历。

8.2 核心思路：前序找根，中序分家

思路只有两步，但非常漂亮。

第一步，前序遍历的第一个元素一定是整棵树的根。 这是“根左右”口诀的直接推论：前序最先访问根。 在我们例子里，前序第一个是 A，所以根就是 A。

第二步，在中序遍历里找到根的位置，根左边是左子树的所有节点， 根右边是右子树的所有节点。这是“左根右”口诀的直接推论。 中序里 A 在中间：左边是 D、B、G、E，共 4 个节点， 所以左子树有 4 个节点；右边是 C、F，共 2 个节点，所以右子树有 2 个。

有了左子树的大小，就能回到前序里把序列切开： 前序第一个 A 是根，接下来 4 个 B、D、E、G 是左子树的前序， 最后 2 个 C、F 是右子树的前序。 于是问题缩小成两个相同的小问题： 用“前序 B、D、E、G + 中序 D、B、G、E”重建左子树； 用“前序 C、F + 中序 C、F”重建右子树。 递归地重复这两步，整棵树就被“切”出来了。

下面这张图展示了第一次分治的完整结构：

8.3 为什么能唯一重建，以及后续预告

为什么前序 + 中序能唯一确定一棵二叉树？因为中序提供了 “哪些节点在左边、哪些在右边”的划分信息， 前序提供了“谁先当根”的顺序信息；两者合起来， 每一步的根和左右子树范围都被唯一确定。 同理，中序 + 后序也能重建（后序的最后一个元素是根）； 层序 + 中序也可以，但划分时要按层序顺序找根， 实现细节更多。单独只有一种遍历通常不行： 前序（或后序、层序）单独给出时，树的形状有歧义， 除非额外记录 null 占位——这正是 6.3 节序列化在做的事。

8.4 算法骨架：递归分治

把思路翻译成算法，骨架只有四步。 先准备一张哈希表，记录中序序列里每个值的位置 （假设节点值互不重复），方便 O(1) 查找； 然后写一个递归函数，参数是当前子树在前序、中序里的范围：

1. 前序范围的第一个值就是根，创建根节点；
2. 在哈希表中查出根在中序里的位置 pos；
3. 中序里 pos 左边是左子树范围、右边是右子树范围， 左子树大小 = pos 减去中序左边界；
4. 用左子树大小切分前序范围，分别递归构造左右子树。

每次递归确定一个根，并把两个范围缩小； 范围为空时返回 null。每一层递归只做常数次查找和切分， 所以总时间是 O(n)，空间 O(n)（哈希表加递归栈）。 如果节点值有重复，中序里会有多个候选位置， 需要额外的规则或遍历所有候选，复杂度随之上升—— 这也是题目通常会声明“值互不相同”的原因。

这段只是骨架预告：完整代码、边界处理和迭代写法， 会留到本系列正式讲“由遍历构造二叉树”时再展开。 现在你只需要记住十个字——前序找根、中序分家、递归切分。

这个“重建”问题在本系列后续文章中会正式展开 （比如“由前序与中序构造二叉树”），本篇先埋下钩子。 而下一篇第 7 篇要讲的是二叉搜索树——你会看到， 中序遍历对二叉搜索树有着特殊意义， “有序”这个性质会第一次把树的形状和值的比较联系起来。

9 结尾：速查表、自测题与下一篇预告

9.1 四种遍历速查表

把全篇最核心的信息压缩成一张小表，贴在脑子里：

遍历	顺序	核心结构	空间	记忆点
前序	根 → 左 → 右	递归 / 栈	O(h)	根在前，复制树
中序	左 → 根 → 右	递归 / 栈	O(h)	根在中间，BST 有序
后序	左 → 右 → 根	递归 / 栈	O(h)	根在后，先算子树
层序	逐层从左到右	队列	O(w)	层层扫，队列绕

再配三句“体检口诀”：时间上，四种都是 O(n)，每个节点访问一次； 空间上，前中后看高度 h，层序看宽度 w； 选择上，找最近用层序，找路径用深度优先。

9.2 自测题

如果五道题都答对了，恭喜你，BFS 的骨架已经长在脑子里了。 如果哪一道卡住了，建议回到对应的章节： 第 1 题回第 2 节手算，第 2 题回 6.1 节， 第 3 题回 6.2 节，第 4 题回 5.2 节的复杂度对比表， 第 5 题回 6.3 节的反序列化。

9.3 常见面试变形一览

把本篇出现过的“层序变形”汇总成一份清单， 刷题时可以直接对照：

• 普通层序遍历：一维结果，队列版；
• 按层输出：双循环，二维结果；
• 锯齿遍历：按层号反转；
• 自底向上：整体反转；
• 最小深度：第一个叶子；
• 右视图 / 左视图：每层最后一个 / 第一个；
• 最大宽度：节点编号，最右减最左；
• 判断完全二叉树：null 占位 + seenNull；
• 序列化 / 反序列化：null 占位 + 队列重建；
• 每层最大值 / 平均值：层内聚合；
• 最底层最左节点：逐层覆盖最左值，最后留下的就是答案。

你会发现它们全都在“双循环 + 一个变量”的骨架上演化。 掌握了队列和层边界，这一整组题就变成了填空题。

9.4 常见疑问速答

最后集中回答几个反复出现的问题。

层序遍历能用递归写吗？ 能，但不推荐。可以带着层号递归： 先访问根（层 0），再递归左子树（层 1）…… 但这样写既没有体现队列思想，还要额外维护层号数组， 代码更复杂，还失去了 BFS “从近到远、可提前终止”的优势。 面试时如果被问到，能说出“递归可以但队列更自然”即可。

为什么有的题解里层序数组没有 null？ 两种约定并存。 不含 null 的序列只保存真实节点，适合“只关心值”的场景； 含 null 的序列保留了空位，适合“需要还原形状”的场景 （完全二叉树判断、序列化）。写代码前先看清题目约定， 这是最容易踩的坑之一。

同一棵树的层序结果唯一吗？ 唯一。约定“从左到右” 之后，每一层的访问顺序都被树的结构唯一确定， 不存在第二种层序。反过来，同一个层序值序列 可能对应不同形状的树，所以“只有值序列”无法唯一还原形状； 必须配合 null 占位或另一种遍历。

队列里的节点是引用还是副本？ 是引用。 JavaScript 里入队的是节点对象本身，不是值的拷贝； 所以遍历过程中对节点做的任何修改（比如改 val、挂孩子） 都会反映到原树上。这一点在做树的变换题时特别重要： 不要在访问节点时顺手修改它，除非你确实想改。

head 指针版本里，队列什么时候为空？ 当 head 等于 数组长度时。head 指向下一个要出队的元素，数组长度是 队尾之后的位置；两者相等，说明中间没有任何元素。 这也是为什么循环条件写的是 head < queue.length 而不是 queue.length > 0——后者的写法配合 shift 可以， 配合 head 指针就会出错。写代码时，把“队列的两种表示” 和各自的判空条件配对记忆，能省下不少调试时间。

9.5 下一篇预告

下一篇是《树系列第 7 篇：二叉搜索树》。 我们会把“值的大小”这个维度加进树里： 左子树的所有节点都小于根，右子树的所有节点都大于根。 你会发现，二叉搜索树把查找变成了沿着一条路径往下走的问题， 中序遍历则能直接输出有序序列——而这两件事， 一篇用 DFS 的“定向行走”，一篇用层序的“从近到远”， 都只是树的遍历思想在不同结构上的应用。 树系列的故事，才刚刚讲到最精彩的地方。

最后，用一句话收束全篇：深度优先是沿路径走的探险家， 广度优先是逐层推进的扫描仪。前序、中序、后序 回答了“根在什么时候被访问”，层序回答了“谁在更浅的层”； 四种遍历合在一起，就是我们对一棵树全部的系统性走法。 下一篇，我们将走进二叉搜索树， 看“值的大小”如何让树的形状自己说话。

（本篇完）