二叉树层序遍历：从BFS原理到LeetCode高频变体实战
1. 从“遍历”到“分层”：为什么层序遍历是面试官的宠儿
如果你刚开始刷LeetCode或者准备面试，二叉树的各种遍历方式一定是绕不开的。前序、中序、后序，这些基于深度优先搜索（DFS）的遍历，大家可能已经滚瓜烂熟了。但面试官常常会微微一笑，抛出一个不那么“常规”的问题：“写一下二叉树的层序遍历吧。” 这时候，如果你还停留在递归的思维里，可能就会卡壳。层序遍历，或者说广度优先搜索（BFS）在二叉树上的应用，考察的不仅仅是你会不会写代码，更是你对数据结构（队列）的理解、对问题分层处理的逻辑，以及将递归思维转换为迭代思维的能力。在实际开发中，这种“一层一层”处理数据的场景比比皆是，比如社交网络中的好友关系扩散、多级组织架构的渲染、任务调度中的优先级执行等。今天，我们就来彻底搞懂二叉树的层序遍历，从最基础的实现，到几种常见的变体，再到面试中那些“坑”，让你下次遇到时能从容应对。
2. 核心武器：队列与广度优先搜索
层序遍历的核心思想非常直观：从根节点开始，先访问第一层（根节点），然后访问第二层（根节点的左右孩子），接着是第三层……以此类推。关键在于，我们访问节点的顺序，必须严格按照层级从上到下、每层从左到右（通常情况）进行。
这和我们熟悉的DFS递归“一条路走到黑”的思路完全不同。递归会先深入最左下的节点，而我们需要的是“广撒网”。这时，一个先进先出（FIFO）的数据结构——队列（Queue），就成了我们的最佳拍档。
2.1 队列的工作原理与选择
你可以把队列想象成一个管道，或者食堂打饭的队伍。元素从一端（队尾）进入，从另一端（队头）离开。在层序遍历中，我们正是利用这个特性来保证访问顺序：
- 先把根节点放入队列。
- 当队列不为空时，进行循环： a. 从队头取出一个节点并访问它。 b. 将这个节点的左孩子（如果存在）放入队尾。 c. 将这个节点的右孩子（如果存在）放入队尾。
这个过程就像是一个“扩散”的过程：每次处理一个节点时，都把它下一层的“火种”（子节点）加入到待处理的队伍末尾，从而保证了同一层的节点一定会比下一层的节点先被处理。
在Java中，我们通常使用LinkedList作为Queue的实现类，因为它提供了高效的入队（offer/add）和出队（poll/remove）操作。
Queue<TreeNode> queue = new LinkedList<>();注意：虽然
ArrayDeque也可以作为队列使用，并且在某些纯队列操作中性能可能略好，但LinkedList作为Queue的标准实现更为常见和直观，在面试和日常编码中都是首选。
2.2 基础模板代码实现
理解了原理，代码就水到渠成了。我们先定义二叉树的节点类，这是所有操作的基础。
// 二叉树节点定义 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } }接下来是层序遍历的核心方法。它接收一个二叉树的根节点，返回一个列表（List），里面按层序遍历的顺序存储了所有节点的值。
public List<Integer> levelOrder(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; // 处理空树的情况 } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); // 根节点入队 while (!queue.isEmpty()) { TreeNode currentNode = queue.poll(); // 队头节点出队 result.add(currentNode.val); // 访问该节点 // 将其左右子节点按顺序入队 if (currentNode.left != null) { queue.offer(currentNode.left); } if (currentNode.right != null) { queue.offer(currentNode.right); } } return result; }这段代码就是一个最标准的、不带任何额外格式要求的层序遍历。它会输出类似[3, 9, 20, 15, 7]这样的结果，其中数字代表节点的值。但面试中，单纯的“遍历”往往只是第一步。
3. 面试高频变体一：按层分组输出
LeetCode上经典的102. 二叉树的层序遍历题目，要求返回的结果是“层序列表的列表”，即每一层的节点值需要单独放在一个子列表里。例如，对于二叉树[3,9,20,null,null,15,7]，需要返回[[3], [9,20], [15,7]]。
这个需求非常普遍，因为它清晰地展现了树的结构。实现的关键在于，我们需要在遍历过程中，知道当前层有多少个节点。
3.1 关键技巧：在每一层遍历开始前记录队列大小
我们无法在遍历中途“感知”层的变化，但可以在处理某一层之前，先看一眼当前队列里有多少个节点。这些节点一定全部属于同一层（为什么？因为上一层的节点在出队时，才将下一层的节点入队，所以在处理新一层开始时，队列里只有新一层的节点）。
public List<List<Integer>> levelOrderWithGroups(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { // 关键步骤：记录当前层的节点数量 int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); // 只处理当前层的这 levelSize 个节点 for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevel.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } // 将当前层的结果加入总结果 result.add(currentLevel); } return result; }为什么这个方法有效？内层的for循环是关键。在循环开始前，levelSize固定了本次循环只出队（处理）这么多个节点，这些节点恰好是上一轮循环中入队的、属于同一层的所有节点。在循环体内，我们将这些节点的子节点（即下一层节点）入队，但本次循环不会处理它们，留到下一次外层while循环。这样就完美地实现了分层。
3.2 一个容易掉入的思维陷阱
一个常见的错误写法是在循环条件里直接使用queue.size()：
// 错误示例！ while (!queue.isEmpty()) { List<Integer> level = new ArrayList<>(); // 错误：queue.size()在循环中会动态变化！ for (int i = 0; i < queue.size(); i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); }这样写会导致for循环的终止条件i < queue.size()在每次迭代后都被重新计算。当你处理第一个节点并将其子节点入队后，queue.size()可能并没有减少（例如，出一个，进两个），导致循环次数超出预期，逻辑完全混乱。务必在循环开始前用变量固定住当前层的节点数，这是此类问题的固定套路。
4. 面试高频变体二：“之”字形层序遍历
这是103. 二叉树的锯齿形层序遍历题目。要求奇数层（假设根节点为第1层）从左到右输出，偶数层从右到左输出。结果类似[[3], [20,9], [15,7]]。
这个变体在按层分组的基础上，增加了一个“方向”的控制。核心思路是：
- 我们仍然需要按层处理。
- 用一个布尔值
leftToRight（或整数level）来标记当前层的输出方向。 - 在将当前层节点值加入列表时，根据方向决定是尾插（正序）还是头插（逆序）。
4.1 使用双端队列（Deque）或结果列表反转
有两种主流实现方式，第一种更直观，利用LinkedList的双端队列特性，在添加元素时选择方向。
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> nodeQueue = new LinkedList<>(); nodeQueue.offer(root); boolean leftToRight = true; // 方向标志，初始为从左到右 while (!nodeQueue.isEmpty()) { int levelSize = nodeQueue.size(); // 使用LinkedList便于在头部插入 LinkedList<Integer> levelList = new LinkedList<>(); for (int i = 0; i < levelSize; i++) { TreeNode currentNode = nodeQueue.poll(); // 根据方向决定插入位置 if (leftToRight) { levelList.addLast(currentNode.val); // 正序，加在尾部 } else { levelList.addFirst(currentNode.val); // 逆序，加在头部 } // 子节点入队的顺序永远是先左后右，保证下一层节点在队列中的物理顺序正确 if (currentNode.left != null) nodeQueue.offer(currentNode.left); if (currentNode.right != null) nodeQueue.offer(currentNode.right); } result.add(levelList); leftToRight = !leftToRight; // 切换方向 } return result; }这里有一个非常重要的细节：无论输出方向如何，子节点入队的顺序永远是先左后右。这保证了队列中节点存储的物理顺序始终是下一层从左到右的顺序。我们只是在“收集结果”这一步，通过改变插入levelList的位置来模拟反向输出。如果入队顺序也随方向改变，整个逻辑会变得极其复杂且容易出错。
第二种方法是常规按层遍历后，对需要逆序的层的结果列表进行反转。
// ... 前面按层遍历的逻辑，得到 result ... for (int i = 0; i < result.size(); i++) { if (i % 2 == 1) { // 假设根节点是第0层，则奇数层反转 Collections.reverse(result.get(i)); } }这种方法代码更简洁，但反转操作Collections.reverse的时间复杂度是O(k)（k为层节点数），而双端队列头插法的时间复杂度是O(1)。在面试中，能说出两种方法的区别并实现第一种，通常会更受青睐。
5. 从层序序列构建二叉树
层序遍历的另一个重要应用是反序列化：如何根据一个层序遍历的数组（如LeetCode常用的输入格式[3,9,20,null,null,15,7]），重新构建出原始的二叉树？这是一个非常实用的技能，因为我们在本地调试时，经常需要快速从数组构造一棵树。
5.1 构建算法：队列的再次登场
构建过程是遍历的逆过程，同样需要队列辅助。核心思想是：用队列维护当前待构建子树的父节点。
- 创建根节点，并入队。
- 遍历输入数组的后续元素（从索引1开始），每次取两个元素（分别作为左孩子和右孩子的值）。
- 从队列中取出一个节点作为当前父节点。
- 如果取得的数组元素不是
null，就创建左孩子节点，并将其挂到父节点下，同时将这个左孩子节点入队（因为它未来也要成为父节点）。 - 对右孩子重复步骤4。
- 继续循环，直到数组遍历完毕。
public TreeNode buildTree(Integer[] nums) { if (nums == null || nums.length == 0 || nums[0] == null) { return null; } TreeNode root = new TreeNode(nums[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; // 从数组的第二个元素开始处理 while (i < nums.length && !queue.isEmpty()) { TreeNode parent = queue.poll(); // 构建左孩子 if (i < nums.length) { Integer leftVal = nums[i++]; if (leftVal != null) { parent.left = new TreeNode(leftVal); queue.offer(parent.left); } // 注意：如果leftVal是null，我们什么都不做，parent.left保持为null } // 构建右孩子 if (i < nums.length) { Integer rightVal = nums[i++]; if (rightVal != null) { parent.right = new TreeNode(rightVal); queue.offer(parent.right); } } } return root; }5.2 处理空节点（null）的边界情况
这是构建过程中最容易出错的地方。在LeetCode的序列化格式中，null表示一个空位。在我们的算法中：
- 当遇到
null时，我们不为父节点创建对应的子节点（即子节点引用保持null）。 - 关键点：只有非
null的节点才需要入队。因为只有非null的节点在未来才可能拥有自己的孩子需要被构建。如果你错误地将null节点也入队，那么在后续轮次中从队列中取出null并试图访问其.left或.right时，就会抛出NullPointerException。
6. 性能考量与空间复杂度分析
对于层序遍历，时间和空间复杂度的分析是面试必问环节。
- 时间复杂度 O(N)：每个节点恰好入队一次、出队一次并访问一次，N为节点总数。这是最优情况，无法再优化。
- 空间复杂度 O(W)：其中W是树的最大宽度（即最宽那一层的节点数）。在最坏情况下（完美二叉树），最后一层的节点数约为N/2，因此空间复杂度也可以表示为O(N)。队列是消耗额外空间的主要来源。
这里有一个常见的误解：有人认为递归实现的DFS空间复杂度是O(logN)（树高），而BFS的O(N)更差。这并不完全准确。DFS递归的空间消耗在于调用栈的深度，在最坏情况（链表状的树）下，深度为N，空间复杂度也是O(N)。BFS的空间消耗在于队列的宽度。对于一棵非常“宽”而“浅”的树，BFS可能消耗更多内存；对于一棵非常“深”而“瘦”的树，DFS递归可能风险更大（栈溢出）。因此，选择哪种方式需要根据树的实际形态和问题需求来决定。
7. 实战中的技巧与避坑指南
在实际编码和面试中，除了算法本身，还有一些细节能体现你的熟练度。
1. 队列操作的选择：在Java中，Queue接口的offer/poll/peek与add/remove/element是两组方法。它们的主要区别在于对异常的处理。offer在队列满时返回false，add则抛出异常；poll在队列空时返回null，remove则抛出异常。在层序遍历这种我们自己控制流程的场景下，队列不可能满，使用offer和poll是更安全、更通用的选择。
2. 节点访问的时机：一定要在节点从队列中poll出来之后，再访问它的值并将其加入结果集。有初学者曾尝试在子节点入队时（queue.offer(node.left)）就将其值加入结果，这会导致顺序错乱，因为同一层的右兄弟节点可能还没入队。
3. 处理超大层级：当树的宽度极大时（例如百万级别），存储整层结果的List<Integer>可能会引发内存压力。在某些极端场景下（如流式处理），可能需要逐节点输出或分批处理，而不是一次性收集整层结果。虽然面试不常考，但知道这个限制能体现你的思考深度。
4. 非二叉树的层序遍历：层序遍历的思想可以轻易推广到N叉树。只需要将处理左右孩子的代码，替换成一个遍历所有子节点的循环即可。这提醒我们，BFS是一种图算法，二叉树只是图的特例。
掌握二叉树的层序遍历，绝不仅仅是背下一个模板。它代表了你对队列这一数据结构的深刻理解，以及将迭代逻辑应用于树形结构的能力。从基础实现到按层分组，再到锯齿形遍历和反序列化构建，这一系列问题层层递进，构成了一个完整的知识考察链。下次面试官再问你层序遍历，你不妨在写完基础代码后，主动问一句：“您是否需要按层分组输出？或者考察一下锯齿形遍历？” 这或许会成为你的加分项。