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 resultBFS思路解析初始化队列将根节点入队记录当前队列大小即当前层的节点数遍历当前层的所有节点出队节点并访问将子节点入队将当前层结果加入最终结果重复直到队列为空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递归思路解析使用递归深度优先搜索通过参数记录当前节点所在的层数根据层数将节点值放入对应的列表中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 depth5.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 depth5.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 核心要点要点说明遍历方式广度优先搜索BFS数据结构使用队列Queue关键技巧记录每层的节点数量时间复杂度O(n)6.2 BFS与DFS对比特性BFS层序DFS前/中/后序遍历顺序按层访问深度优先数据结构队列栈递归调用栈空间复杂度O(n)O(h)适用场景最短路径、层序处理树的遍历、分治6.3 扩展思考如何实现层序遍历的迭代版本层序遍历和DFS遍历在内存使用上有什么区别在什么情况下BFS比DFS更合适参考资料LeetCode 102 题解广度优先搜索
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 resultBFS思路解析初始化队列将根节点入队记录当前队列大小即当前层的节点数遍历当前层的所有节点出队节点并访问将子节点入队将当前层结果加入最终结果重复直到队列为空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递归思路解析使用递归深度优先搜索通过参数记录当前节点所在的层数根据层数将节点值放入对应的列表中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 depth5.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 depth5.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 核心要点要点说明遍历方式广度优先搜索BFS数据结构使用队列Queue关键技巧记录每层的节点数量时间复杂度O(n)6.2 BFS与DFS对比特性BFS层序DFS前/中/后序遍历顺序按层访问深度优先数据结构队列栈递归调用栈空间复杂度O(n)O(h)适用场景最短路径、层序处理树的遍历、分治6.3 扩展思考如何实现层序遍历的迭代版本层序遍历和DFS遍历在内存使用上有什么区别在什么情况下BFS比DFS更合适参考资料LeetCode 102 题解广度优先搜索
