我来给你讲解 LeetCode 第 102 题「二叉树的层序遍历」。

题目描述

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

示例：

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

解题思路详解

第一步：理解什么是层序遍历

层序遍历（BFS，广度优先搜索）的特点是按层级顺序访问节点：

• 先访问根节点（第1层）
• 然后访问根节点的所有子节点（第2层）
• 再访问第2层所有节点的子节点（第3层）
• 以此类推...

这种遍历方式需要用到队列这种数据结构。

第二步：基础思路 - 使用队列

基本算法步骤：

1. 将根节点入队
2. 当队列不为空时循环：
   • 出队一个节点，访问它
   • 将该节点的左子节点入队（如果存在）
   • 将该节点的右子节点入队（如果存在）

但是，这样只能得到所有节点的顺序，无法区分不同层级。

第三步：如何区分不同层级

关键技巧：在每一层开始前，记录当前队列的长度（即该层的节点数），然后一次性处理完这一层的所有节点。

具体步骤：

1. 创建队列，将根节点入队
2. 当队列不为空时：
   • 获取当前队列的长度 levelSize（这就是当前层的节点数）
   • 创建一个临时列表 currentLevel 存储当前层的节点值
   • 循环 levelSize 次：
     • 出队一个节点
     • 将节点值加入 currentLevel
     • 将该节点的左右子节点入队（如果存在）
   • 将 currentLevel 加入结果列表
3. 返回结果列表

第四步：详细示例演示

以示例 [3,9,20,null,null,15,7] 为例：

初始状态：

• 队列：[3]
• 结果：[]

第1层处理：

• 队列长度 = 1
• 出队节点3，currentLevel = [3]
• 入队节点3的子节点：9, 20
• 队列：[9, 20]
• 结果：[[3]]

第2层处理：

• 队列长度 = 2
• 出队节点9，currentLevel = [9]
• 节点9无子节点
• 出队节点20，currentLevel = [9, 20]
• 入队节点20的子节点：15, 7
• 队列：[15, 7]
• 结果：[[3], [9,20]]

第3层处理：

• 队列长度 = 2
• 出队节点15，currentLevel = [15]
• 节点15无子节点
• 出队节点7，currentLevel = [15, 7]
• 节点7无子节点
• 队列：[]
• 结果：[[3], [9,20], [15,7]]

第五步：代码实现（详细注释）

from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result = []  # 存储最终结果
    queue = deque([root])  # 队列，初始包含根节点
    
    while queue:
        level_size = len(queue)  # 当前层的节点数
        current_level = []  # 存储当前层的节点值
        
        # 处理当前层的所有节点
        for _ in range(level_size):
            node = queue.popleft()  # 出队
            current_level.append(node.val)  # 记录节点值
            
            # 将子节点入队（先左后右）
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)  # 将当前层加入结果
    
    return result

第六步：复杂度分析

• 时间复杂度：O(n)，其中 n 是节点数，每个节点恰好被访问一次
• 空间复杂度：O(n)，队列中最多存储一层的节点数，最坏情况下是 O(n)

第七步：关键要点总结

1. 队列是核心：使用队列来按顺序处理节点
2. 层级分离技巧：在每层开始前记录队列长度，确保同一层的节点被一起处理
3. 边界处理：空树的特殊情况
4. 顺序保持：先左子节点后右子节点入队，保证从左到右的顺序

这种层序遍历的思想是很多二叉树相关问题的基础，比如求二叉树的最大宽度、锯齿形层序遍历等。