Hot 100 --- 二叉树的层序遍历

本文概览：本文以LeetCode题目"二叉树的层序遍历"为例，详细讲解BFS（广度优先搜索）的原理和实现，重点说明为什么用队列、队列如何保证层序、以及如何按层分组输出

一、题目

二、题目分析

题目要求按层从上到下、从左到右遍历二叉树，每一层的节点值放在一个列表中，最终返回一个列表的列表

比如：

3 / \ 9 20 / \ 15 7 输出：[[3], [9, 20], [15, 7]]

这道题的核心就是BFS（广度优先搜索），也叫层序遍历。和之前用递归（DFS）“一根筋往下钻"不同，BFS 是"一层一层扫”

思路概览

Java 实现代码如下

publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>res=newArrayList<>();if(root==null){returnres;}Queue<TreeNode>queue=newLinkedList<>();// 根节点入队queue.offer(root);while(!queue.isEmpty()){// 当前层的节点数intsize=queue.size();List<Integer>list=newArrayList<>();// 逐个处理当前层的节点for(inti=0;i<size;i++){TreeNodenode=queue.poll();list.add(node.val);// 左孩子入队if(node.left!=null){queue.offer(node.left);}// 右孩子入队if(node.right!=null){queue.offer(node.right);}}res.add(list);}returnres;}

思路简要说明

1. 用队列来控制遍历顺序，先进先出，保证从左到右
2. 每轮开始前记录队列大小size，这就是当前层的节点数
3. 逐个出队当前层的节点，把值加入结果；同时把左右孩子依次入队
4. 一轮结束，当前层处理完毕，队列里剩下的是下一层的节点

三、思路详解

DFS vs BFS：两种遍历思路

先回顾一下中序遍历（DFS），它的遍历路径是"一根筋往下钻"：

3 / \ 9 20 / \ 15 7 中序遍历（DFS）：9 → 3 → 15 → 20 → 7 先一条路走到黑（9），再回退，再走到黑（15），再回退... 深度优先，纵向展开

而层序遍历（BFS）是"一层一层扫"：

3 / \ 9 20 / \ 15 7 层序遍历（BFS）：[3] → [9, 20] → [15, 7] 先扫第一层，再扫第二层，再扫第三层... 广度优先，横向展开

DFS 是"先往深处走"，BFS 是"先往宽处走"。DFS 靠递归实现，BFS 靠队列实现

为什么用队列？

BFS 的核心数据结构是队列（Queue）。队列的特性是先进先出（FIFO），这正好满足"按层顺序处理"的需求

想一想：要按层遍历，就必须先处理上层的节点，再处理下层的节点。队列的先进先出保证了：

• 当前层的节点先入队，所以先出队
• 孩子节点后入队，所以等当前层都出完了，下一层才轮到出队

用一个形象的比喻：队列就像一条排队的通道。当前层的人在前面处理，处理完一个就把他的"孩子"（下一层的节点）排到队伍末尾。等前面这一批人都处理完了，下一批人自然就排到了队伍前面

整个流程可以概括为一句话：把当前层的节点依次出队，出队的同时把它们的孩子依次入队

怎么按层分组？

题目要求每一层的节点放在一个单独的列表中，所以关键问题是：怎么区分哪些节点属于同一层？

答案在于：每轮开始前，队列里恰好只有当前层的节点

为什么？因为上一轮出队时，把当前层的节点都出完了，只留下了它们的孩子们（即下一层的节点）。所以每轮开始时queue.size()就是当前层的节点数

这个size非常关键——它告诉我们这轮要出队几个节点。用 for 循环精确地出队size个节点，就不会多出下一层的节点

size必须在 for 循环外记录。如果放在循环条件里用queue.size()，因为循环中会往队列加入新节点（孩子），大小会不断变化，导致一轮处理了多层的节点

图解完整过程

3 / \ 9 20 / \ 15 7

初始：队列 = [3]

第 1 轮（处理第 1 层）：

当前队列大小 = 1，说明第 1 层有 1 个节点

队列：[3] 出队 3 → 加入结果 [3] 3 有左孩子 9 → 入队 3 有右孩子 20 → 入队 队列变为：[9, 20]

第 2 轮（处理第 2 层）：

当前队列大小 = 2，说明第 2 层有 2 个节点

队列：[9, 20] 出队 9 → 加入结果 [3, 9] 9 没有左孩子 9 没有右孩子 队列变为：[20] 出队 20 → 加入结果 [3, 9, 20] 20 有左孩子 15 → 入队 20 有右孩子 7 → 入队 队列变为：[15, 7]

第 3 轮（处理第 3 层）：

当前队列大小 = 2，说明第 3 层有 2 个节点

队列：[15, 7] 出队 15 → 加入结果 [3, 9, 20, 15] 15 没有左孩子 15 没有右孩子 队列变为：[7] 出队 7 → 加入结果 [3, 9, 20, 15, 7] 7 没有左孩子 7 没有右孩子 队列变为：[]（空）

队列空了，遍历结束。最终结果按层分组：[[3], [9, 20], [15, 7]]

可以看到，每一轮开始时队列中恰好是当前层的所有节点。这是因为上一轮出队当前层节点的同时，把它们的孩子（下一层节点）入队了。等当前层全部出队完毕，队列里就只剩下下一层的节点

入队顺序：先左后右

题目要求从左到右遍历，所以入队顺序必须是先左孩子后右孩子。因为队列是先进先出的，先入队的先出队，所以先入队左孩子就能保证同一层中左边的节点先被处理

如果先入队右孩子再入队左孩子，同一层的节点就会变成从右到左的顺序，不符合题目要求

复杂度分析

• 时间复杂度：O(n)，每个节点恰好入队一次、出队一次
• 空间复杂度：O(n)，队列中最多同时存放一层节点，最坏情况（完全二叉树最后一层）约为 n/2 个节点