LeetCode102.二叉树层序遍历

目录

1. 层序遍历算法详解
2. 核心代码逐行解释
3. 从列表构建二叉树
4. 两个过程的对比分析
5. 完整测试代码

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,val=0,left=None,right=None):self.val=val self.left=left self.right=rightclassSolution:deflevelOrder(self,root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult

2.2 关键代码详解

第 1 行：queue = deque([root])

queue=deque([root])

问题：为什么是[root]而不是root？

• deque需要一个可迭代对象作为参数
• [root]是一个只包含根节点的列表
• 如果用deque(root)，会尝试遍历root对象，但TreeNode不是可迭代的，会报错

等价写法：

# 写法 1：直接传入包含 root 的列表（最简洁）queue=deque([root])# 写法 2：先创建空队列，再添加 rootqueue=deque()queue.append(root)

为什么用deque而不是list？

BFS 需要频繁从队列头部取元素，deque性能更优。

第 2 行：level_size = len(queue)

level_size=len(queue)

这是核心技巧！

作用：在每层开始时记录当前层的节点数量，确保for循环只处理当前层的节点。

如果没有level_size会怎样？

# 错误写法whilequeue:node=queue.popleft()current_level.append(node.val)# 这样会把所有节点都放在一个列表里，无法分层

结果会是：[[3, 9, 20, 15, 7]]（所有节点混在一起）

正确写法：

whilequeue:level_size=len(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_size=1# 队列长度为 1current_level=[]# for 循环执行 1 次node=queue.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_size=2# 队列长度为 2current_level=[]# for 循环执行 2 次# 第 1 次：处理节点 9node=queue.popleft()# node = 9current_level.append(9)# [9]# 节点 9 没有子节点# 第 2 次：处理节点 20node=queue.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_size=2# 队列长度为 2current_level=[]# for 循环执行 2 次# 第 1 次：处理节点 15node=queue.popleft()# node = 15current_level.append(15)# [15]# 第 2 次：处理节点 7node=queue.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 7

3.2 完整代码

defbuild_tree(values):""" 根据层序遍历的列表创建二叉树 """ifnotvaluesorvalues[0]isNone:returnNoneroot=TreeNode(values[0])queue=deque([root])i=1whilequeueandi<len(values):node=queue.popleft()# 处理左子节点ifi<len(values)andvalues[i]isnotNone:node.left=TreeNode(values[i])queue.append(node.left)i+=1# 处理右子节点ifi<len(values)andvalues[i]isnotNone:node.right=TreeNode(values[i])queue.append(node.right)i+=1returnroot

3.3 执行流程详解

示例输入：[3, 9, 20, None, None, 15, 7]

【第 1 步：初始化】

root=TreeNode(3)# 创建根节点queue=deque([root])# 队列：[节点 3]i=1# 索引从 1 开始

树结构： 3 (root) 队列：[3] 索引 i=1

【第 2 步：第 1 轮循环】

node=queue.popleft()# 取出节点 3# 处理左子节点 (values[1] = 9)node.left=TreeNode(9)queue.append(node.left)# 队列：[9]i=2# 处理右子节点 (values[2] = 20)node.right=TreeNode(20)queue.append(node.right)# 队列：[9, 20]i=3

树结构： 3 / \ 9 20 队列：[9, 20] 索引 i=3

【第 3 步：第 2 轮循环】

node=queue.popleft()# 取出节点 9# 处理左子节点 (values[3] = None)# 不创建节点i=4# 处理右子节点 (values[4] = None)# 不创建节点i=5

树结构： 3 / \ 9 20 队列：[20] 索引 i=5

【第 4 步：第 3 轮循环】

node=queue.popleft()# 取出节点 20# 处理左子节点 (values[5] = 15)node.left=TreeNode(15)queue.append(node.left)# 队列：[15]i=6# 处理右子节点 (values[6] = 7)node.right=TreeNode(7)queue.append(node.right)# 队列：[15, 7]i=7

树结构： 3 / \ 9 20 / \ 15 7 队列：[15, 7] 索引 i=7

【第 5 步：结束】

# i=7, len(values)=7，退出循环returnroot

3.4 完整执行过程表格

4. 两个过程的对比分析

4.1 核心对比

4.2 代码对比

build_tree 代码结构

defbuild_tree(values):root=TreeNode(values[0])# 创建根节点queue=deque([root])i=1whilequeueandi<len(values):node=queue.popleft()# 取出父节点# 创建左子节点ifvalues[i]isnotNone:node.left=TreeNode(values[i])# 创建节点queue.append(node.left)# 加入队列i+=1# 创建右子节点ifvalues[i]isnotNone:node.right=TreeNode(values[i])# 创建节点queue.append(node.right)# 加入队列i+=1returnroot

levelOrder 代码结构

deflevelOrder(root):result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()# 取出节点current_level.append(node.val)# 读取值ifnode.left:queue.append(node.left)# 加入队列ifnode.right:queue.append(node.right)# 加入队列result.append(current_level)returnresult

4.3 关键差异

1. 节点操作不同

2. 索引处理不同

3. 分层处理不同

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. 从列表构建树tree=build_tree([3,9,20,None,None,15,7])# 2. 从树得到列表result=levelOrder(tree)# 3. 扁平化结果flattened=[valforlevelinresultforvalinlevel]# flattened = [3, 9, 20, 15, 7]# 4. 注意：None 值在 levelOrder 中不会被记录# 所以完全还原需要特殊处理 None 值

4.6 时间和空间复杂度对比

5. 完整测试代码

fromcollectionsimportdequefromtypingimportOptional,List# Definition for a binary tree node.classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightclassSolution:deflevelOrder(self,root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.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:returnNoneroot=TreeNode(values[0])queue=deque([root])i=1whilequeueandi<len(values):node=queue.popleft()# 处理左子节点ifi<len(values)andvalues[i]isnotNone:node.left=TreeNode(values[i])queue.append(node.left)i+=1# 处理右子节点ifi<len(values)andvalues[i]isnotNone:node.right=TreeNode(values[i])queue.append(node.right)i+=1returnroot# 测试函数deftest_level_order():solution=Solution()# 测试用例 1: 示例树print("测试 1: [3,9,20,None,None,15,7]")tree1=build_tree([3,9,20,None,None,15,7])result1=solution.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]")tree2=build_tree([1])result2=solution.levelOrder(tree2)print(f"结果：{result2}")print(f"期望：[[1]]")print(f"通过：{result2==[[1]]}\n")# 测试用例 3: 空树print("测试 3: []")tree3=build_tree([])result3=solution.levelOrder(tree3)print(f"结果：{result3}")print(f"期望：[]")print(f"通过：{result3==[]}\n")# 测试用例 4: 只有左子树print("测试 4: [1,2,3,None,None,4]")tree4=build_tree([1,2,3,None,None,4])result4=solution.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]")tree5=build_tree([1,2,3,4,5,6,7])result5=solution.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]")tree6=build_tree([1,None,2,None,3])result6=solution.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 核心要点

1. 层序遍历使用 BFS + 队列实现
2. level_size是分层的关键技巧
3. deque比list更适合队列操作
4. build_tree和levelOrder互为逆过程