目录层序遍历算法详解核心代码逐行解释从列表构建二叉树两个过程的对比分析完整测试代码1. 层序遍历算法详解1.1 问题描述LeetCode 第 102 题二叉树的层序遍历要求按照从上到下、从左到右的顺序遍历二叉树的每一层并将每一层的结果作为一个列表返回。1.2 示例输入二叉树 3 / \ 9 20 / \ 15 7 输出[[3], [9, 20], [15, 7]]1.3 核心思路使用广度优先搜索 (BFS)和队列来实现层序遍历。关键点使用队列存储待处理的节点每层开始时记录当前层的节点数量level_size只处理当前层的节点下一层的节点在下一轮循环中处理2. 核心代码逐行解释2.1 完整代码fromcollectionsimportdequefromtypingimportOptional,ListclassTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:deflevelOrder(self,root:Optional[TreeNode])-List[List[int]]:ifnotroot:return[]result[]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)returnresult2.2 关键代码详解第 1 行queue deque([root])queuedeque([root])问题为什么是[root]而不是rootdeque需要一个可迭代对象作为参数[root]是一个只包含根节点的列表如果用deque(root)会尝试遍历root对象但TreeNode不是可迭代的会报错等价写法# 写法 1直接传入包含 root 的列表最简洁queuedeque([root])# 写法 2先创建空队列再添加 rootqueuedeque()queue.append(root)为什么用deque而不是list操作dequelistpopleft()O(1)O(n)append()O(1)O(1)BFS 需要频繁从队列头部取元素deque性能更优。第 2 行level_size len(queue)level_sizelen(queue)这是核心技巧作用在每层开始时记录当前层的节点数量确保for循环只处理当前层的节点。如果没有level_size会怎样# 错误写法whilequeue:nodequeue.popleft()current_level.append(node.val)# 这样会把所有节点都放在一个列表里无法分层结果会是[[3, 9, 20, 15, 7]]所有节点混在一起正确写法whilequeue:level_sizelen(queue)# 关键记录当前层节点数current_level[]for_inrange(level_size):# 只处理当前层# ...result.append(current_level)# 分层存储结果[[3], [9, 20], [15, 7]]2.3 完整执行流程示例二叉树3 / \ 9 20 / \ 15 7【初始状态】队列[3] result: [] level_size: 1【第 1 轮 while 循环】level_size1# 队列长度为 1current_level[]# for 循环执行 1 次nodequeue.popleft()# node 3current_level.append(3)# [3]queue.append(9)# 队列[9]queue.append(20)# 队列[9, 20]result.append([3])# result [[3]]3 ✓ / \ 9 20 ← 在队列中 / \ 15 7【第 2 轮 while 循环】level_size2# 队列长度为 2current_level[]# for 循环执行 2 次# 第 1 次处理节点 9nodequeue.popleft()# node 9current_level.append(9)# [9]# 节点 9 没有子节点# 第 2 次处理节点 20nodequeue.popleft()# node 20current_level.append(20)# [9, 20]queue.append(15)# 队列[15]queue.append(7)# 队列[15, 7]result.append([9,20])# result [[3], [9, 20]]3 / \ 9 20 ✓ / \ 15 7 ← 在队列中【第 3 轮 while 循环】level_size2# 队列长度为 2current_level[]# for 循环执行 2 次# 第 1 次处理节点 15nodequeue.popleft()# node 15current_level.append(15)# [15]# 第 2 次处理节点 7nodequeue.popleft()# node 7current_level.append(7)# [15, 7]result.append([15,7])# result [[3], [9, 20], [15, 7]]【结束】# 队列为空退出循环return[[3],[9,20],[15,7]]3. 从列表构建二叉树3.1 问题背景为了测试层序遍历算法我们需要从列表创建二叉树。例如[3,9,20,None,None,15,7]应该创建3 / \ 9 20 / \ 15 73.2 完整代码defbuild_tree(values): 根据层序遍历的列表创建二叉树 ifnotvaluesorvalues[0]isNone:returnNonerootTreeNode(values[0])queuedeque([root])i1whilequeueandilen(values):nodequeue.popleft()# 处理左子节点ifilen(values)andvalues[i]isnotNone:node.leftTreeNode(values[i])queue.append(node.left)i1# 处理右子节点ifilen(values)andvalues[i]isnotNone:node.rightTreeNode(values[i])queue.append(node.right)i1returnroot3.3 执行流程详解示例输入[3, 9, 20, None, None, 15, 7]【第 1 步初始化】rootTreeNode(3)# 创建根节点queuedeque([root])# 队列[节点 3]i1# 索引从 1 开始树结构 3 (root) 队列[3] 索引 i1【第 2 步第 1 轮循环】nodequeue.popleft()# 取出节点 3# 处理左子节点 (values[1] 9)node.leftTreeNode(9)queue.append(node.left)# 队列[9]i2# 处理右子节点 (values[2] 20)node.rightTreeNode(20)queue.append(node.right)# 队列[9, 20]i3树结构 3 / \ 9 20 队列[9, 20] 索引 i3【第 3 步第 2 轮循环】nodequeue.popleft()# 取出节点 9# 处理左子节点 (values[3] None)# 不创建节点i4# 处理右子节点 (values[4] None)# 不创建节点i5树结构 3 / \ 9 20 队列[20] 索引 i5【第 4 步第 3 轮循环】nodequeue.popleft()# 取出节点 20# 处理左子节点 (values[5] 15)node.leftTreeNode(15)queue.append(node.left)# 队列[15]i6# 处理右子节点 (values[6] 7)node.rightTreeNode(7)queue.append(node.right)# 队列[15, 7]i7树结构 3 / \ 9 20 / \ 15 7 队列[15, 7] 索引 i7【第 5 步结束】# i7, len(values)7退出循环returnroot3.4 完整执行过程表格轮次当前节点values[i] 左values[i] 右队列变化i 变化初始---[3]11节点 3920[9, 20]1→32节点 9NoneNone[20]3→53节点 20157[15, 7]5→7结束---[15, 7]74. 两个过程的对比分析4.1 核心对比特性build_tree(列表→树)levelOrder(树→列表)目的根据列表创建二叉树遍历二叉树生成列表方向列表 → 树树 → 列表关系层序遍历的逆过程层序遍历的正过程队列作用按层序顺序创建节点按层序顺序访问节点4.2 代码对比build_tree 代码结构defbuild_tree(values):rootTreeNode(values[0])# 创建根节点queuedeque([root])i1whilequeueandilen(values):nodequeue.popleft()# 取出父节点# 创建左子节点ifvalues[i]isnotNone:node.leftTreeNode(values[i])# 创建节点queue.append(node.left)# 加入队列i1# 创建右子节点ifvalues[i]isnotNone:node.rightTreeNode(values[i])# 创建节点queue.append(node.right)# 加入队列i1returnrootlevelOrder 代码结构deflevelOrder(root):result[]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)returnresult4.3 关键差异1. 节点操作不同过程操作类型代码示例build_tree创建节点node.left TreeNode(values[i])levelOrder读取节点current_level.append(node.val)2. 索引处理不同过程索引使用build_tree需要i跟踪列表位置每轮i 2levelOrder不需要索引直接遍历队列3. 分层处理不同过程分层方式build_tree不需要分层按顺序创建即可levelOrder需要level_size控制每层节点数4.4 队列操作对比build_tree 的队列操作初始queue [3] 第 1 轮 - 取出3 - 创建9, 20 - 加入9, 20 - 队列[9, 20] 第 2 轮 - 取出9 - 创建无 (None) - 加入无 - 队列[20] 第 3 轮 - 取出20 - 创建15, 7 - 加入15, 7 - 队列[15, 7]levelOrder 的队列操作初始queue [3] 第 1 轮 - 取出3 - 读取3 - 加入9, 20 - 队列[9, 20] - 结果[[3]] 第 2 轮 - 取出9, 20 - 读取9, 20 - 加入15, 7 - 队列[15, 7] - 结果[[3], [9, 20]] 第 3 轮 - 取出15, 7 - 读取15, 7 - 加入无 - 队列[] - 结果[[3], [9, 20], [15, 7]]4.5 互为逆过程的证明正向levelOrder树 → 列表 输入 3 / \ 9 20 / \ 15 7 输出[3, 9, 20, None, None, 15, 7]逆向build_tree列表 → 树 输入[3, 9, 20, None, None, 15, 7] 输出 3 / \ 9 20 / \ 15 7验证# 1. 从列表构建树treebuild_tree([3,9,20,None,None,15,7])# 2. 从树得到列表resultlevelOrder(tree)# 3. 扁平化结果flattened[valforlevelinresultforvalinlevel]# flattened [3, 9, 20, 15, 7]# 4. 注意None 值在 levelOrder 中不会被记录# 所以完全还原需要特殊处理 None 值4.6 时间和空间复杂度对比算法时间复杂度空间复杂度说明build_treeO(n)O(n)n 为列表长度队列最多存储一层的节点levelOrderO(n)O(n)n 为节点总数队列最多存储一层的节点5. 完整测试代码fromcollectionsimportdequefromtypingimportOptional,List# Definition for a binary tree node.classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:deflevelOrder(self,root:Optional[TreeNode])-List[List[int]]:ifnotroot:return[]result[]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# 辅助函数根据列表创建二叉树defbuild_tree(values): 根据层序遍历的列表创建二叉树 例如[3,9,20,None,None,15,7] 会创建 3 / \ 9 20 / \ 15 7 ifnotvaluesorvalues[0]isNone:returnNonerootTreeNode(values[0])queuedeque([root])i1whilequeueandilen(values):nodequeue.popleft()# 处理左子节点ifilen(values)andvalues[i]isnotNone:node.leftTreeNode(values[i])queue.append(node.left)i1# 处理右子节点ifilen(values)andvalues[i]isnotNone:node.rightTreeNode(values[i])queue.append(node.right)i1returnroot# 测试函数deftest_level_order():solutionSolution()# 测试用例 1: 示例树print(测试 1: [3,9,20,None,None,15,7])tree1build_tree([3,9,20,None,None,15,7])result1solution.levelOrder(tree1)print(f结果{result1})print(f期望[[3], [9, 20], [15, 7]])print(f通过{result1[[3],[9,20],[15,7]]}\n)# 测试用例 2: 单节点print(测试 2: [1])tree2build_tree([1])result2solution.levelOrder(tree2)print(f结果{result2})print(f期望[[1]])print(f通过{result2[[1]]}\n)# 测试用例 3: 空树print(测试 3: [])tree3build_tree([])result3solution.levelOrder(tree3)print(f结果{result3})print(f期望[])print(f通过{result3[]}\n)# 测试用例 4: 只有左子树print(测试 4: [1,2,3,None,None,4])tree4build_tree([1,2,3,None,None,4])result4solution.levelOrder(tree4)print(f结果{result4})print(f期望[[1], [2, 3], [4]])print(f通过{result4[[1],[2,3],[4]]}\n)# 测试用例 5: 完全二叉树print(测试 5: [1,2,3,4,5,6,7])tree5build_tree([1,2,3,4,5,6,7])result5solution.levelOrder(tree5)print(f结果{result5})print(f期望[[1], [2, 3], [4, 5, 6, 7]])print(f通过{result5[[1],[2,3],[4,5,6,7]]}\n)# 测试用例 6: 斜树只有右子节点print(测试 6: [1,None,2,None,3])tree6build_tree([1,None,2,None,3])result6solution.levelOrder(tree6)print(f结果{result6})print(f期望[[1], [2], [3]])print(f通过{result6[[1],[2],[3]]}\n)if__name____main__:print(*50)print(二叉树层序遍历测试)print(*50\n)test_level_order()print(*50)print(所有测试完成)print(*50)测试结果 二叉树层序遍历测试 测试 1: [3,9,20,None,None,15,7] 结果[[3], [9, 20], [15, 7]] 期望[[3], [9, 20], [15, 7]] 通过True 测试 2: [1] 结果[[1]] 期望[[1]] 通过True 测试 3: [] 结果[] 期望[] 通过True 测试 4: [1,2,3,None,None,4] 结果[[1], [2, 3], [4]] 期望[[1], [2, 3], [4]] 通过True 测试 5: [1,2,3,4,5,6,7] 结果[[1], [2, 3], [4, 5, 6, 7]] 期望[[1], [2, 3], [4, 5, 6, 7]] 通过True 测试 6: [1,None,2,None,3] 结果[[1], [2], [3]] 期望[[1], [2], [3]] 通过True 所有测试完成 6. 总结6.1 核心要点层序遍历使用 BFS 队列实现level_size是分层的关键技巧deque比list更适合队列操作build_tree和levelOrder互为逆过程