LeetCode 102：二叉树的层序遍历 | BFS

LeetCode 102：二叉树的层序遍历 | BFS

一、题目详解

1.1 题目描述

LeetCode 102：二叉树的层序遍历（Binary Tree Level Order Traversal）

给你二叉树的根节点root，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

难度：Medium

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1] 输出：[[1]]

示例 3：

输入：root = [] 输出：[]

1.2 题目分析

层序遍历也称为广度优先搜索（BFS），与前序、中序、后序遍历（深度优先搜索）不同，层序遍历按层次从上到下、从左到右访问节点。

二、算法实现

2.1 BFS实现（使用队列）

from collections import deque def levelOrder(root): if not root: return [] result = [] queue = deque([root]) while queue: level = [] size = len(queue) for _ in range(size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result

BFS思路解析：

1. 初始化队列，将根节点入队
2. 记录当前队列大小（即当前层的节点数）
3. 遍历当前层的所有节点：
   • 出队节点并访问
   • 将子节点入队
4. 将当前层结果加入最终结果
5. 重复直到队列为空

2.2 递归实现

def levelOrder_recursive(root): result = [] def bfs(node, level): if not node: return # 如果当前层还没有对应的列表，创建一个 if len(result) == level: result.append([]) # 将当前节点值加入对应层 result[level].append(node.val) # 递归处理子节点，层数+1 bfs(node.left, level + 1) bfs(node.right, level + 1) bfs(root, 0) return result

递归思路解析：

1. 使用递归深度优先搜索
2. 通过参数记录当前节点所在的层数
3. 根据层数将节点值放入对应的列表中

2.3 按层输出（自底向上）

def levelOrderBottom(root): if not root: return [] result = [] queue = deque([root]) while queue: level = [] size = len(queue) for _ in range(size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.insert(0, level) # 插入到列表开头 return result

三、复杂度分析

3.1 BFS实现

• 时间复杂度：O(n)，每个节点入队出队一次
• 空间复杂度：O(n)，最坏情况（完全二叉树最后一层）需要存储 n/2 个节点

3.2 递归实现

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(h)，递归调用栈的深度

四、边界情况讨论

4.1 空树

root = None # 输出：[]

4.2 单节点树

root = TreeNode(1) # 输出：[[1]]

4.3 完全二叉树

# 1 # / \ # 2 3 # / \ / \ # 4 5 6 7 # 输出：[[1], [2, 3], [4, 5, 6, 7]]

4.4 只有左子树

# 1 # / # 2 # / # 3 # 输出：[[1], [2], [3]]

五、应用场景

5.1 求树的最大深度

def maxDepth(root): if not root: return 0 depth = 0 queue = deque([root]) while queue: depth += 1 size = len(queue) for _ in range(size): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth

5.2 求树的最小深度

def minDepth(root): if not root: return 0 depth = 0 queue = deque([root]) while queue: depth += 1 size = len(queue) for _ in range(size): node = queue.popleft() # 找到叶子节点，返回当前深度 if not node.left and not node.right: return depth if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth

5.3 层序遍历的变种

# 锯齿形层序遍历（之字形） def zigzagLevelOrder(root): if not root: return [] result = [] queue = deque([root]) left_to_right = True while queue: level = [] size = len(queue) for _ in range(size): node = queue.popleft() if left_to_right: level.append(node.val) else: level.insert(0, node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) left_to_right = not left_to_right return result

六、总结

6.1 核心要点

6.2 BFS与DFS对比

6.3 扩展思考

1. 如何实现层序遍历的迭代版本？
2. 层序遍历和DFS遍历在内存使用上有什么区别？
3. 在什么情况下BFS比DFS更合适？

参考资料：

• LeetCode 102 题解
• 广度优先搜索