二叉树层序遍历：BFS核心思想与LeetCode实战解析

1. 从一道高频面试题说起：为什么层序遍历如此重要？

如果你正在准备技术面试，或者已经开始在LeetCode上刷题，那么“二叉树的层序遍历”这道题，你几乎不可能错过。它不仅是LeetCode题库中的经典题目（编号102），更是面试官考察候选人基础数据结构掌握程度和编码能力的“试金石”。很多朋友可能会觉得，不就是遍历嘛，前序、中序、后序都搞定了，层序能有多难？但恰恰是这种看似简单的题目，最能暴露问题：你是否真正理解了队列（Queue）在算法中的应用？你是否能清晰地将问题分解为“访问当前层”和“准备下一层”两个步骤？你的代码在处理空树、单节点树等边界情况时是否健壮？

更重要的是，层序遍历的思想是许多更复杂算法的基础模板。比如，求二叉树的最大深度、最小深度、判断是否为完全二叉树、寻找每层的最大值、甚至是在图中进行广度优先搜索（BFS），其核心框架都脱胎于层序遍历。可以说，吃透了层序遍历，你就拿到了打开“树与图”相关算法大门的一把关键钥匙。今天，我们就抛开那些笼统的概念，深入到代码和场景里，手把手拆解层序遍历的几种实现方式、背后的核心思想，以及如何应对它的各种“变体”题目。

2. 核心武器：队列（Queue）与广度优先搜索（BFS）

要理解层序遍历，首先必须理解其背后的核心机制：广度优先搜索（Breadth-First Search, BFS）。这与我们之前熟悉的前序、中序、后序遍历（它们都属于深度优先搜索DFS）有本质区别。

深度优先（DFS）像是一个执着探险家，选择一条岔路走到黑，直到尽头再返回，用递归或栈（Stack）来实现，体现的是“后进先出”（LIFO）的思想。

广度优先（BFS）则像是一位稳扎稳打的将军，先把当前所在据点（根节点）的所有直接下属（子节点）都探查清楚，再让这些下属各自去探查他们的直接下属。它需要一种“先进先出”（FIFO）的数据结构来保证这个顺序，这就是队列（Queue）。

想象一下这个场景：你站在一棵树的树根（根节点）。你的任务是按层记录所有节点的值。

1. 你首先看到根节点，记下它的值。
2. 接着，你需要去看根节点的直接孩子（左孩子和右孩子）。但你看完左孩子后，不能立刻深入去看左孩子的孩子，因为那样就变成深度优先了。你必须先把根节点的所有孩子都“登记在册”。
3. 队列就在这里发挥作用了。你把根节点放入队列。当处理（访问）完队首的节点后，你将其左右孩子（如果存在）依次加入到队列的末尾。这样，队列就自动帮你维护了“先被发现的节点先被访问”的顺序，从而天然地实现了按层遍历。

这个过程可以抽象为以下步骤，这也是层序遍历最核心的模板：

1. 初始化一个队列，将根节点入队（如果根节点不为空）。
2. while循环，条件为队列不为空： a. 记录当前队列的长度size（这个size就是当前层的节点数量）。 b. 创建一个列表level，用于存储当前层的节点值。 c. 进行一个内层循环，循环size次： i. 从队首弹出一个节点node。 ii. 将node.val加入level列表。 iii. 如果node有左孩子，将左孩子入队。 iv. 如果node有右孩子，将右孩子入队。 d. 将存储好的level列表加入最终的结果列表。
3. 返回结果列表。

这个模板是解决所有层序遍历及相关问题的基石，务必理解并熟记。

3. 标准实现：LeetCode 102. 二叉树的层序遍历

现在，让我们用代码将上述思想具体化。题目要求返回一个二维列表，每个子列表对应二叉树的一层。

我们以Python为例，因为其语法清晰，易于理解。其他语言逻辑完全一致。

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right from collections import deque class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: # 边界情况处理：空树直接返回空列表 return [] result = [] # 最终结果 queue = deque([root]) # 使用deque作为队列，初始化时放入根节点 while queue: # 当队列不为空时，说明还有节点未处理 level_size = len(queue) # 关键步骤：记录当前层的节点数 current_level = [] # 存储当前层节点的值 for _ in range(level_size): # 只处理当前层的level_size个节点 node = queue.popleft() # 从队首弹出节点 current_level.append(node.val) # 访问该节点 # 将该节点的子节点（下一层的节点）加入队列 if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) # 将当前层的结果加入最终列表 return result

代码逐行解析与避坑点：

1. from collections import deque：在Python中，使用deque（双端队列）作为队列比使用list（pop(0)操作是O(n)复杂度）效率高得多，因为它的popleft()和append()操作都是O(1)复杂度。这是写BFS/层序遍历时的一个必备优化技巧。
2. if not root: return []：这是一个非常重要的边界条件检查。如果输入是一棵空树，你的代码应该返回一个空列表，而不是报错或返回None。面试中遗漏边界检查是常见的扣分点。
3. level_size = len(queue)：这是层序遍历区别于普通BFS最核心的一行代码。在进入每一层的处理之前，我们先获取当前队列的长度，这个长度就代表了当前层所有节点的数量。随后我们只循环level_size次，这样就严格保证了内层循环for _ in range(level_size)只处理当前层的节点，无论循环体内我们向队列中添加了多少下一层的节点（node.left和node.right），都不会影响本轮循环。这是实现“分层”的关键。
4. 循环顺序：内层循环中，一定是先popleft()获取节点，然后处理该节点（append(val)），最后才将其子节点入队。这个顺序不能乱。
5. 子节点入队判断：在将左、右孩子入队前，一定要判断它们是否为空。将None入队会导致后续循环出错，并且浪费空间。

这个标准模板的时间复杂度是O(n)，其中n是树中的节点数，因为每个节点恰好入队和出队各一次。空间复杂度在最坏情况下（完全二叉树）也是O(n)，因为队列中最多会存储差不多一层的节点数，对于完全二叉树，最后一层节点数约为n/2。

4. 层序遍历的常见变体与解题思路

掌握了标准模板，很多LeetCode上的题目就变成了“换汤不换药”的练习。它们都在考察你是否能灵活运用这个BFS框架。下面我们看几个典型变体。

4.1 变体一：自底向上的层序遍历（LeetCode 107）

题目要求：返回其节点值自底向上的层序遍历结果。即，从最底层开始，逐层向上。

思路：我们完全可以先使用标准模板得到“自顶向下”的结果，然后将这个结果列表反转即可。这是一种“结果处理”型的变体，不改变遍历过程本身。

class Solution: def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) # 核心变化：将结果反转 return result[::-1] # 或者使用 result.reverse(); return result

注意：这里result[::-1]创建了一个新列表。如果题目对空间有极致要求，可以使用result.reverse()原地修改。

4.2 变体二：二叉树的锯齿形层序遍历（LeetCode 103）

题目要求：先从左往右，再从右往左，以此类推，进行层序遍历。

思路：遍历的框架不变，依然是一层一层地处理。变化在于，我们记录每一层节点值时，需要判断当前是第几层（从0开始计数）。如果是偶数层（0， 2， 4...），则按正常顺序（从左到右）记录；如果是奇数层（1， 3， 5...），则按逆序记录。逆序可以通过在将current_level加入result前反转实现，或者更高效地，在向current_level添加值时，根据层数决定是append（尾部添加）还是insert(0, ...)（头部插入），但后者时间复杂度较高。通常采用事后反转列表的方式。

class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] result = [] queue = deque([root]) left_to_right = True # 标志位，True表示当前层从左到右 while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() # 根据方向决定添加顺序 if left_to_right: current_level.append(node.val) # 尾部添加，正序 else: current_level.insert(0, node.val) # 头部插入，实现逆序。注意：频繁insert(0)效率低。 # 子节点入队顺序始终不变（先左后右），以保证下一层的节点顺序正确 if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) left_to_right = not left_to_right # 切换方向 return result

更优的实现：为了避免insert(0)的O(n)操作，我们可以始终按append正序收集当前层，只是在将current_level加入result前，判断是否需要反转。

while queue: ... for _ in range(level_size): node = queue.popleft() current_level.append(node.val) # 始终正序添加 ... # 如果是奇数层，反转当前层列表 if not left_to_right: current_level.reverse() result.append(current_level) left_to_right = not left_to_right

4.3 变体三：在每个树行中找最大值（LeetCode 515）

题目要求：找出二叉树每一层的最大值。

思路：框架完全不变。在每一层的内层循环中，我们不再需要维护整个current_level列表，只需要一个变量（如max_val）来追踪当前层遍历过程中遇到的最大值即可。

class Solution: def largestValues(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) level_max = float('-inf') # 初始化为负无穷大 for _ in range(level_size): node = queue.popleft() level_max = max(level_max, node.val) # 更新当前层最大值 if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level_max) # 记录该层最大值 return result

4.4 变体四：填充每个节点的下一个右侧节点指针（LeetCode 116）

题目要求：给定一个完美二叉树，将所有next指针指向其同一层的右侧节点。如果右侧没有节点，则设置为NULL。

思路：这题将层序遍历的应用从“收集值”提升到了“修改树结构”。我们依然使用BFS模板。关键点在于，在内层循环处理同一层的节点时，除了最后一个节点，当前节点的next应该指向队列中的下一个节点（即当前层的下一个节点）。由于我们是一边弹出一边处理，队列的队首始终是当前层的下一个待处理节点。但注意，我们在处理节点i时，队列里可能已经包含了它的子节点（下一层的节点），所以不能直接用queue[0]作为next。我们需要在循环开始前保存prev_node（前一个节点），然后在处理当前节点时，将prev_node.next指向它。

# Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next from collections import deque class Solution: def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': if not root: return None queue = deque([root]) while queue: level_size = len(queue) prev_node = None # 初始化前一个节点为None for i in range(level_size): node = queue.popleft() # 如果不是该层第一个节点，将前一个节点的next指向当前节点 if prev_node: prev_node.next = node prev_node = node # 更新前一个节点为当前节点 # 子节点入队 if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 该层最后一个节点的next默认为None，符合要求 return root

5. 深度思考：层序遍历与递归（DFS）的关联

看到这里，你可能会想，层序遍历必须用迭代（队列）吗？能用递归（DFS）实现吗？答案是肯定的，但这需要一点技巧。递归本质上是深度优先，如何让它产出广度优先（分层）的结果呢？

思路是：在递归过程中，我们额外传递一个表示当前深度的参数level。结果列表result的索引i就对应树的第i层。当我们访问到一个节点时，我们就将它添加到result[level]对应的那个子列表中。如果result的长度小于等于level，说明我们是第一次到达这一层，需要先为这一层创建一个新列表。

class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: result = [] def dfs(node, depth): if not node: return # 如果结果列表的长度等于当前深度，说明需要为这一层新建一个列表 if len(result) == depth: result.append([]) # 将节点值添加到其对应的层列表中 result[depth].append(node.val) # 递归遍历左右子树，深度+1 dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root, 0) return result

这种方法非常巧妙，它利用了递归遍历的顺序（前序），但通过depth参数将节点值“分发”到了不同的层级容器中。它的时间复杂度和空间复杂度（考虑递归调用栈）也是O(n)。在面试中，如果你能先给出迭代的队列解法，再补充这种递归的DFS解法，并清晰解释其原理，通常会是一个很大的加分项，因为这展示了你对树遍历不同维度的理解。

6. 实战中的陷阱与性能优化

理论懂了，代码也会写了，但在实际刷题和面试中，还有一些细节陷阱需要注意。

陷阱一：忘记处理空树。这是最基础的错误，但紧张时容易忽略。务必在函数开头判断if not root:。

陷阱二：错误地使用列表作为队列。在Python中，用list.pop(0)来模拟队列出队操作的时间复杂度是O(n)，因为需要移动其后所有元素。这在数据量大时会成为性能瓶颈。务必使用collections.deque的popleft()。

陷阱三：level_size的获取时机错误。一定要在while循环内部，for循环之前获取level_size = len(queue)。如果你写成for i in range(len(queue)):，并且在循环内pop和append，那么len(queue)会在每次循环时重新计算，导致循环次数失控，无法正确分层。

陷阱四：在锯齿形遍历中，错误地改变子节点入队顺序。无论本层的输出顺序是正序还是逆序，子节点（下一层的节点）入队的顺序必须始终保持一致（通常是先左后右）。改变入队顺序会打乱树本身的结构关系，导致后续遍历完全错误。我们只改变收集结果的顺序，不改变遍历探索的顺序。

性能优化考量：

1. 队列选择：如前所述，使用deque。
2. 结果存储：在确定问题不需要保留中间状态的情况下，可以考虑用一维列表存储所有结果，然后在循环外根据level_size信息重新划分层次。但这通常不会带来质的提升，代码清晰度更重要。
3. 空间优化：对于“填充下一个右侧节点指针”这类问题，有空间复杂度O(1)的解法（利用已建立的next指针），这属于进阶优化，在掌握BFS解法后可以进一步研究。

7. 从层序遍历到更广阔的图BFS

最后，我想强调层序遍历的普适性。二叉树是一种特殊的图（每个节点最多有两个子节点的有向无环图）。因此，二叉树的层序遍历算法，其实就是图论中广度优先搜索（BFS）在二叉树这种特定结构上的应用。

在图BFS中，我们同样需要一个队列和一个记录已访问节点的集合（对于二叉树，由于结构简单且无环，通常不需要显式的“已访问”集合，因为子节点不会指回父节点）。核心步骤一模一样：

1. 将起始节点入队并标记为已访问。
2. 当队列不为空时，取出队首节点。
3. 遍历该节点的所有“邻居”（在二叉树中是左、右孩子；在图中是相邻节点）。
4. 对于每个未访问过的邻居，将其入队并标记为已访问。

所以，当你彻底掌握了二叉树的层序遍历，你实际上已经掌握了BFS算法的核心思想。这对于后续学习岛屿数量（LeetCode 200）、打开转盘锁（LeetCode 752）、单词接龙（LeetCode 127）等基于图的BFS题目，打下了坚实的基础。你会发现，它们的代码结构和二叉树层序遍历如出一辙，只是“邻居”的定义和“已访问”的处理变得更加复杂而已。

刷题不是死记硬背模板，而是理解算法思想，并能在不同场景下识别出问题的本质，灵活运用所学工具。层序遍历就是一个绝佳的起点，它简单到足以让你看清BFS的全貌，又重要到贯穿了整个算法学习的中后期。希望这篇详细的拆解，能帮你把这块基石打牢。下次遇到相关的题目，不妨先问问自己：这道题，是不是可以用层序遍历（BFS）的思路来解决？