LeetCode 102. 二叉树的层序遍历 详细技术解析

LeetCode 102. 二叉树的层序遍历 详细技术解析本文针对 LeetCode 102. 二叉树的层序遍历 问题从题目解析、核心思路、代码实现、边界处理到面试拓展进行全方位拆解适合算法入门及进阶开发者阅读附完整可运行代码、测试案例及避坑指南严格贴合题目要求的代码格式。一、题目核心解析1.1 题目描述精准版给定一棵二叉树的根节点 root返回其节点值的层序遍历结果。层序遍历要求逐层地、从左到右访问所有节点最终返回一个二维列表其中每个子列表对应二叉树的一层子列表内的元素为该层节点值的顺序左到右。1.2 关键信息提炼避坑重点核心要求「逐层访问」「从左到右」结果按「层分组」二维列表一层一个子列表区别于前序、中序、后序的深度优先遍历边界场景根节点为null空树返回空列表树只有一个节点返回包含单个子列表的二维列表树有多层且存在叶子节点左右子树为空数据范围节点数 0~2000时间复杂度需控制在 O(n)n为节点数空间复杂度 O(n)最坏情况为满二叉树最后一层节点数为 n/2核心考点二叉树的广度优先搜索BFS应用队列的使用先进先出适配逐层访问逻辑。1.3 示例拆解直观理解层序遍历逻辑示例 1典型多层树输入root [3,9,20,null,null,15,7]二叉树结构如下 3 / \ 9 20 / \ 15 7 解析 1. 第1层根节点只有节点3 → 子列表 [3] 2. 第2层根节点的左右子树从左到右为9、20 → 子列表 [9,20] 3. 第3层20的左右子树从左到右为15、7 → 子列表 [15,7] 4. 无更多层级最终结果为 [[3],[9,20],[15,7]] 输出[[3],[9,20],[15,7]]示例 2单节点树输入root [1]仅根节点 解析只有1层子列表为 [1] 输出[[1]]示例 3空树输入root []根节点为null 解析无任何节点返回空列表 输出[]二、解题思路拆解从原理到实现层序遍历的核心是「广度优先搜索BFS」区别于深度优先搜索DFS的“一条路走到黑”BFS是“逐层推进”刚好适配层序遍历的需求。而实现BFS的核心数据结构是「队列」先进先出FIFO通过队列控制节点的访问顺序确保每层节点全部处理完后再处理下一层。2.1 核心思路BFS 队列利用队列的先进先出特性实现逐层访问步骤如下特殊处理若根节点为null空树直接返回空列表初始化创建一个队列将根节点入队创建一个二维列表用于存储最终的层序遍历结果循环处理队列直到队列为空记录当前队列的长度即当前层的节点数关键确保只处理当前层的节点不混入下一层创建一个临时子列表用于存储当前层的所有节点值遍历当前层的所有节点循环次数 当前层节点数出队一个节点将其值加入临时子列表若该节点有左子节点将左子节点入队保证下一层节点按顺序入队若该节点有右子节点将右子节点入队左先右后符合“从左到右”要求当前层遍历结束将临时子列表加入最终结果的二维列表中队列清空后返回最终的二维列表。2.2 关键细节避坑核心必须记录「当前层节点数」这是区分“当前层”和“下一层”的关键若不记录会导致将下一层节点混入当前层处理最终结果错乱队列的入队顺序左子节点先入队右子节点后入队确保每层节点按“从左到右”的顺序访问空树处理根节点为null时直接返回空列表避免队列初始化报错节点值的存储每层遍历结束后必须将临时子列表加入最终结果不可直接在最终列表中追加节点值会导致层级混乱。2.3 常见误区避坑指南误区1不记录当前层节点数直接遍历队列所有元素导致不同层级的节点混入同一个子列表误区2左子节点和右子节点入队顺序颠倒导致每层节点顺序为“从右到左”不符合题目要求误区3忽略空树场景root null直接初始化队列并入队导致空指针异常误区4临时子列表未及时清空导致下一层节点值追加到上一层的子列表中。2.4 复杂度分析时间复杂度O(n)n为二叉树的节点数每个节点仅入队、出队各一次遍历一次空间复杂度O(n)最坏情况为满二叉树最后一层有 n/2 个节点队列最多存储 n/2 个节点加上其他层节点总空间不超过n优势效率稳定无论树是斜树、平衡树还是满二叉树时间复杂度均为O(n)适配题目2000个节点的范围。三、完整代码实现贴合题目要求格式代码严格按照题目要求的类和方法格式编写添加详细注释兼顾可读性和正确性可直接复制到 LeetCode 提交通过适配Python3环境处理了所有边界场景空树、单节点、多层树。# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightfromtypingimportList,OptionalfromcollectionsimportdequeclassSolution:deflevelOrder(self,root:Optional[TreeNode])-List[List[int]]: 二叉树的层序遍历广度优先搜索BFS实现 :param root: 二叉树的根节点 :return: 二维列表每个子列表对应一层的节点值从左到右 # 初始化结果列表用于存储每层的节点值result[]# 特殊处理空树根节点为None直接返回空列表ifnotroot:returnresult# 初始化队列用于实现BFS使用deque高效实现入队、出队操作# 队列初始存入根节点开始逐层遍历queuedeque([root])# 循环处理队列直到队列为空所有节点处理完毕whilequeue:# 关键记录当前层的节点数确保只处理当前层的节点level_sizelen(queue)# 临时列表存储当前层的所有节点值current_level[]# 遍历当前层的所有节点循环次数 当前层节点数for_inrange(level_size):# 出队取出当前层的一个节点先进先出nodequeue.popleft()# 将当前节点值加入当前层的临时列表current_level.append(node.val)# 左子节点存在入队左先右后保证从左到右的顺序ifnode.left:queue.append(node.left)# 右子节点存在入队ifnode.right:queue.append(node.right)# 当前层遍历结束将临时列表加入结果列表result.append(current_level)# 所有层处理完毕返回结果returnresult代码说明关键细节队列选择使用 collections.deque 而非列表因为列表的 pop(0) 操作时间复杂度为 O(n)而 deque 的 popleft() 操作时间复杂度为 O(1)提升效率level_size len(queue)每次循环开始时队列中存储的都是当前层的所有节点长度即为当前层节点数确保遍历不越界空树处理先判断 root 是否为 None避免队列初始化时传入空值导致报错节点入队逻辑仅当左/右子节点存在时才入队避免空节点入队占用空间、影响遍历。代码调用示例与题目示例一致# 示例1构造二叉树 [3,9,20,null,null,15,7]root1TreeNode(3)root1.leftTreeNode(9)root1.rightTreeNode(20)root1.right.leftTreeNode(15)root1.right.rightTreeNode(7)solutionSolution()print(solution.levelOrder(root1))# 输出[[3],[9,20],[15,7]]# 示例2构造二叉树 [1]root2TreeNode(1)print(solution.levelOrder(root2))# 输出[[1]]# 示例3空树root Noneroot3Noneprint(solution.levelOrder(root3))# 输出[]四、测试案例与边界情况分析为确保代码鲁棒性梳理6种常见边界场景逐一测试验证覆盖所有易错情况确保代码能通过LeetCode所有测试用例。4.1 边界情况1空树root None输入root None 解析无任何节点返回空列表 输出[]4.2 边界情况2单节点树输入root [5] 解析只有1层子列表为 [5] 输出[[5]]4.3 边界情况3斜树所有节点只有左子树输入root [1,2,null,3,null,4,null,5]结构如下 1 / 2 / 3 / 4 / 5 解析共5层每层只有1个节点 输出[[1],[2],[3],[4],[5]]4.4 边界情况4斜树所有节点只有右子树输入root [1,null,2,null,3,null,4] 解析共4层每层只有1个节点 输出[[1],[2],[3],[4]]4.5 边界情况5满二叉树深度为3输入root [1,2,3,4,5,6,7] 解析 第1层[1] 第2层[2,3] 第3层[4,5,6,7] 输出[[1],[2,3],[4,5,6,7]]4.6 边界情况6不完全二叉树部分节点缺失输入root [1,2,3,null,4,null,5,6]结构如下 1 / \ 2 3 \ \ 4 5 / 6 解析 第1层[1] 第2层[2,3] 第3层[4,5] 第4层[6] 输出[[1],[2,3],[4,5],[6]]五、复杂度总结与面试提示5.1 复杂度总结时间复杂度O(n)n为二叉树节点数每个节点入队、出队各一次无多余遍历空间复杂度O(n)队列最多存储一层的节点最坏情况为满二叉树最后一层节点数为n/2结果列表存储所有节点值空间为O(n)适配性完全满足题目0~2000个节点的范围无超时、内存溢出风险。5.2 面试提示重点本题核心考点广度优先搜索BFS的应用、队列的使用以及层序遍历的“逐层分组”逻辑面试高频提问1为什么用队列实现BFS答队列先进先出的特性刚好适配“逐层访问”先处理当前层所有节点再处理下一层面试高频提问2如果用DFS实现层序遍历该怎么做答通过递归记录当前节点的层级将节点值加入对应层级的子列表中后文拓展思路会详细说明面试高频提问3deque和列表的区别答列表pop(0)是O(n)时间复杂度deque.popleft()是O(1)用deque能提升效率尤其是节点较多时易错点强调必须记录当前层节点数否则会导致层级混乱左子节点先入队保证从左到右的顺序空树需单独处理。六、拓展思路进阶优化6.1 DFS实现层序遍历面试拓展虽然BFS是层序遍历的最优实现但面试中可能会被要求用DFS递归实现核心思路是「记录当前层级」将节点值加入对应层级的子列表代码如下# Definition for a binary tree node.# class TreeNode:# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightfromtypingimportList,OptionalclassSolution:deflevelOrder(self,root:Optional[TreeNode])-List[List[int]]:result[]# 递归辅助函数参数当前节点、当前层级defdfs(node,level):ifnotnode:return# 若当前层级对应的子列表未创建创建子列表iflevellen(result):result.append([])# 将当前节点值加入对应层级的子列表result[level].append(node.val)# 递归处理左子树层级1左先右后dfs(node.left,level1)dfs(node.right,level1)dfs(root,0)# 从根节点、层级0开始递归returnresult说明DFS实现的时间复杂度仍为O(n)空间复杂度为O(h)h为树的高度递归栈深度适合面试中展示思维灵活性但实际开发中BFS更直观、更高效。6.2 优化打印层序遍历带层级标识实际开发中可能需要打印每层的层级标识如“第1层[3]”可在代码中添加层级计数优化输出可读性核心修改如下在BFS代码基础上whilequeue:level_sizelen(queue)current_level[]for_inrange(level_size):nodequeue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)# 打印层级标识可选print(f第{len(result)1}层{current_level})result.append(current_level)七、总结本题是二叉树广度优先搜索BFS的经典应用题难度简单但细节较多核心在于「用队列控制逐层访问」和「按层分组存储结果」。最优实现是「BFS deque队列」代码简洁、效率稳定时间和空间复杂度均为O(n)适配题目所有场景。掌握边界情况空树、单节点、斜树和常见误区能有效提升代码鲁棒性避免面试中因细节出错。面试中除了掌握BFS实现还需了解DFS实现方式展示思维的全面性。如果需要进一步拓展如层序遍历的逆序、之字形层序遍历可留言讨论共同完善解题方案。