LeetCode 102. 二叉树的层序遍历：从理论到实践的完整剖析

LeetCode 102. 二叉树的层序遍历从理论到实践的完整剖析问题描述给你二叉树的根节点root返回其节点值的层序遍历。即逐层地从左到右访问所有节点。示例 1输入root [3,9,20,null,null,15,7] 输出[[3],[9,20],[15,7]]示例 2输入root [1] 输出[[1]]示例 3输入root [] 输出[]算法原理核心思路层序遍历本质上是一种广度优先搜索BFS策略其核心在于使用队列数据结构来实现初始化一个队列并将根节点入队当队列不为空时执行以下操作记录当前队列的长度即当前层的节点数遍历当前层的所有节点出队一个节点将该节点的值加入结果集将该节点的左子节点如果存在入队将该节点的右子节点如果存在入队重复步骤 2直到队列为空复杂度分析时间复杂度O(n)其中 n 是二叉树的节点数。每个节点恰好入队和出队一次。空间复杂度O(n)最坏情况下队列中最多同时存在 O(n) 个节点例如当二叉树是满二叉树时最后一层的节点数约为 n/2。代码实现from collections import deque # Definition for a binary tree node. class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_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代码解析边界处理如果根节点为None直接返回空列表。初始化创建一个双端队列queue并将根节点入队。层序遍历当队列不为空时记录当前层的节点数level_size。创建一个空列表level用于存储当前层的节点值。遍历当前层的所有节点出队一个节点并将其值加入level。如果该节点有左子节点将左子节点入队。如果该节点有右子节点将右子节点入队。将level加入结果集result。返回结果遍历完成后返回result。实战技巧队列的选择在 Python 中我们使用collections.deque来实现队列因为它的popleft()操作是 O(1) 时间复杂度而使用列表的pop(0)操作是 O(n) 时间复杂度会导致整体时间复杂度退化。层的划分通过记录当前队列的长度我们可以精确地划分每一层的节点这是层序遍历的关键技巧。错误分析常见错误忘记处理空树当根节点为None时应直接返回空列表。层的划分错误如果不记录当前队列的长度而是直接遍历队列会导致无法正确划分每一层。队列操作错误在 Python 中使用列表的pop(0)操作会导致时间复杂度升高应使用deque。调试技巧在遍历过程中可以打印出当前队列的状态以便观察层序遍历的过程。对于复杂的二叉树可以画出树的结构手动模拟遍历过程验证算法的正确性。扩展思考变种问题二叉树的锯齿形层序遍历即先从左到右再从右到左交替进行。二叉树的层序遍历 II即从叶子节点所在层到根节点所在层逐层从左到右遍历。N 叉树的层序遍历将二叉树扩展为 N 叉树需要遍历每个节点的所有子节点。应用场景层序遍历在以下场景中有着广泛的应用树的广度优先搜索例如寻找树中的最短路径。树的序列化和反序列化例如将树转换为字符串或从字符串重建树。层次相关的问题例如寻找树的最大深度、最小深度等。个人实践感悟最近在准备转正答辩每天被各种算法题和合并冲突吓醒救命今天刷到这个经典的层序遍历问题突然想到刚实习时第一次遇到这个问题的场景。当时我还不知道用队列直接递归硬刚结果时间复杂度爆炸被mentor嘲笑了一整天麻了现在再看这个问题其实核心就是BFS的思想用队列来管理每一层的节点。这让我意识到算法的学习真的是一个循序渐进的过程从一无所知到熟练掌握需要不断地练习和总结。最后分享一个小技巧在面试中遇到树的遍历问题先想清楚是用DFS还是BFS然后选择合适的数据结构这样可以事半功倍。这就是大佬吗我也要成为这样的人输入输出示例输入输出示例 1输入root [3,9,20,null,null,15,7]输出[[3],[9,20],[15,7]]输入输出示例 2输入root [1]输出[[1]]输入输出示例 3输入root []输出[]结语层序遍历是二叉树中的经典算法掌握它不仅有助于解决相关的LeetCode问题也能帮助我们更好地理解树的结构和BFS的思想。希望这篇文章对大家有所帮助祝大家刷题愉快