1. 从一道高频面试题说起为什么层序遍历如此重要如果你正在准备技术面试或者已经开始在LeetCode上刷题那么“二叉树的层序遍历”这道题你几乎不可能错过。它不仅是LeetCode题库中的经典题目编号102更是面试官考察候选人基础数据结构掌握程度和编码能力的“试金石”。很多朋友可能会觉得不就是遍历嘛前序、中序、后序都搞定了层序能有多难但恰恰是这种看似简单的题目最能暴露问题你是否真正理解了队列Queue在算法中的应用你是否能清晰地将问题分解为“访问当前层”和“准备下一层”两个步骤你的代码在处理空树、单节点树等边界情况时是否健壮更重要的是层序遍历的思想是许多更复杂算法的基础模板。比如求二叉树的最大深度、最小深度、判断是否为完全二叉树、寻找每层的最大值、甚至是在图中进行广度优先搜索BFS其核心框架都脱胎于层序遍历。可以说吃透了层序遍历你就拿到了打开“树与图”相关算法大门的一把关键钥匙。今天我们就抛开那些笼统的概念深入到代码和场景里手把手拆解层序遍历的几种实现方式、背后的核心思想以及如何应对它的各种“变体”题目。2. 核心武器队列Queue与广度优先搜索BFS要理解层序遍历首先必须理解其背后的核心机制广度优先搜索Breadth-First Search, BFS。这与我们之前熟悉的前序、中序、后序遍历它们都属于深度优先搜索DFS有本质区别。深度优先DFS像是一个执着探险家选择一条岔路走到黑直到尽头再返回用递归或栈Stack来实现体现的是“后进先出”LIFO的思想。广度优先BFS则像是一位稳扎稳打的将军先把当前所在据点根节点的所有直接下属子节点都探查清楚再让这些下属各自去探查他们的直接下属。它需要一种“先进先出”FIFO的数据结构来保证这个顺序这就是队列Queue。想象一下这个场景你站在一棵树的树根根节点。你的任务是按层记录所有节点的值。你首先看到根节点记下它的值。接着你需要去看根节点的直接孩子左孩子和右孩子。但你看完左孩子后不能立刻深入去看左孩子的孩子因为那样就变成深度优先了。你必须先把根节点的所有孩子都“登记在册”。队列就在这里发挥作用了。你把根节点放入队列。当处理访问完队首的节点后你将其左右孩子如果存在依次加入到队列的末尾。这样队列就自动帮你维护了“先被发现的节点先被访问”的顺序从而天然地实现了按层遍历。这个过程可以抽象为以下步骤这也是层序遍历最核心的模板初始化一个队列将根节点入队如果根节点不为空。while循环条件为队列不为空 a. 记录当前队列的长度size这个size就是当前层的节点数量。 b. 创建一个列表level用于存储当前层的节点值。 c. 进行一个内层循环循环size次 i. 从队首弹出一个节点node。 ii. 将node.val加入level列表。 iii. 如果node有左孩子将左孩子入队。 iv. 如果node有右孩子将右孩子入队。 d. 将存储好的level列表加入最终的结果列表。返回结果列表。这个模板是解决所有层序遍历及相关问题的基石务必理解并熟记。3. 标准实现LeetCode 102. 二叉树的层序遍历现在让我们用代码将上述思想具体化。题目要求返回一个二维列表每个子列表对应二叉树的一层。我们以Python为例因为其语法清晰易于理解。其他语言逻辑完全一致。# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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代码逐行解析与避坑点from collections import deque在Python中使用deque双端队列作为队列比使用listpop(0)操作是O(n)复杂度效率高得多因为它的popleft()和append()操作都是O(1)复杂度。这是写BFS/层序遍历时的一个必备优化技巧。if not root: return []这是一个非常重要的边界条件检查。如果输入是一棵空树你的代码应该返回一个空列表而不是报错或返回None。面试中遗漏边界检查是常见的扣分点。level_size len(queue)这是层序遍历区别于普通BFS最核心的一行代码。在进入每一层的处理之前我们先获取当前队列的长度这个长度就代表了当前层所有节点的数量。随后我们只循环level_size次这样就严格保证了内层循环for _ in range(level_size)只处理当前层的节点无论循环体内我们向队列中添加了多少下一层的节点node.left和node.right都不会影响本轮循环。这是实现“分层”的关键。循环顺序内层循环中一定是先popleft()获取节点然后处理该节点append(val)最后才将其子节点入队。这个顺序不能乱。子节点入队判断在将左、右孩子入队前一定要判断它们是否为空。将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_right4.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 result4.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 root5. 深度思考层序遍历与递归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)会在每次循环时重新计算导致循环次数失控无法正确分层。陷阱四在锯齿形遍历中错误地改变子节点入队顺序。无论本层的输出顺序是正序还是逆序子节点下一层的节点入队的顺序必须始终保持一致通常是先左后右。改变入队顺序会打乱树本身的结构关系导致后续遍历完全错误。我们只改变收集结果的顺序不改变遍历探索的顺序。性能优化考量队列选择如前所述使用deque。结果存储在确定问题不需要保留中间状态的情况下可以考虑用一维列表存储所有结果然后在循环外根据level_size信息重新划分层次。但这通常不会带来质的提升代码清晰度更重要。空间优化对于“填充下一个右侧节点指针”这类问题有空间复杂度O(1)的解法利用已建立的next指针这属于进阶优化在掌握BFS解法后可以进一步研究。7. 从层序遍历到更广阔的图BFS最后我想强调层序遍历的普适性。二叉树是一种特殊的图每个节点最多有两个子节点的有向无环图。因此二叉树的层序遍历算法其实就是图论中广度优先搜索BFS在二叉树这种特定结构上的应用。在图BFS中我们同样需要一个队列和一个记录已访问节点的集合对于二叉树由于结构简单且无环通常不需要显式的“已访问”集合因为子节点不会指回父节点。核心步骤一模一样将起始节点入队并标记为已访问。当队列不为空时取出队首节点。遍历该节点的所有“邻居”在二叉树中是左、右孩子在图中是相邻节点。对于每个未访问过的邻居将其入队并标记为已访问。所以当你彻底掌握了二叉树的层序遍历你实际上已经掌握了BFS算法的核心思想。这对于后续学习岛屿数量LeetCode 200、打开转盘锁LeetCode 752、单词接龙LeetCode 127等基于图的BFS题目打下了坚实的基础。你会发现它们的代码结构和二叉树层序遍历如出一辙只是“邻居”的定义和“已访问”的处理变得更加复杂而已。刷题不是死记硬背模板而是理解算法思想并能在不同场景下识别出问题的本质灵活运用所学工具。层序遍历就是一个绝佳的起点它简单到足以让你看清BFS的全貌又重要到贯穿了整个算法学习的中后期。希望这篇详细的拆解能帮你把这块基石打牢。下次遇到相关的题目不妨先问问自己这道题是不是可以用层序遍历BFS的思路来解决