好的，我们这次来详细讲解 LeetCode 第 102 题「二叉树的层序遍历」。

这道题是学习树结构时非常经典和重要的题目，也是理解广度优先搜索 (BFS) 的绝佳入门题。

1. 题目描述

题目链接：LeetCode 102

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

示例：
给定二叉树: [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

注意：

• 需要将每一层的节点值分别放在一个子列表中。
• 节点的顺序必须是从左到右。

2. 问题分析与思路形成

我们先来理解一下什么是“层序遍历”。

什么是层序遍历？
想象一下，你站在树的根节点（第一层），你的任务是：

1. 先记录下根节点的值。
2. 然后去记录根节点下一层（第二层）的所有节点的值。
3. 接着记录第三层所有节点的值...
4. 以此类推，直到遍历完整棵树。

这个过程就像是一滴水滴在树根，然后波纹一层一层地向外扩散。这种“由近及远”的遍历方式，就是广度优先搜索 (Breadth-First Search, BFS) 的核心思想。

如何实现这种“一层一层”的访问？
这里我们需要一个非常重要的数据结构：队列 (Queue)。

队列的特性是“先进先出” (FIFO)。这正好符合我们的需求：我们先访问的节点（上一层的节点），它们的子节点（下一层的节点）也应该先被加入等待访问的名单。

核心思路步骤（循序渐进）：

1. 初始化：首先，我们把根节点放入队列中。此时队列里是第一层的全部节点（只有根节点一个）。
2. 开始循环：只要队列不为空，就说明还有节点未被遍历，我们就继续。
3. 处理当前层：
   a. 在每一轮循环开始时，我们先记录一下当前队列的长度，这个长度就代表了当前层的节点数量（比如第一轮循环时，队列里只有根节点，长度为1）。
   b. 我们开始一个内层循环，次数就是刚才记录的长度。在这个内层循环中，我们依次从队列的头部取出节点。
   c. 将取出的节点的值存入一个临时的列表中，代表这一层的遍历结果。
   d. 接着，检查这个节点是否有左孩子和右孩子。如果有，就按照先左后右的顺序将它们加入到队列的尾部。注意：此时加入的节点属于下一层，不会在当前层的内层循环中被处理。
4. 存储结果并进入下一层：当内层循环结束（即当前层的所有节点都已处理完毕），我们将存储了这一层节点值的临时列表，加入到最终的结果列表中。然后开始下一轮大循环，处理队列中已经积累的下一层的所有节点。

这个过程会一直持续，直到队列为空，意味着所有节点都已遍历完毕。

3. 详细解题步骤（配合示例）

我们用一个具体的例子来走一遍流程。二叉树为 [3,9,20,null,null,15,7]。

初始化：

• 队列 queue: [3] （将根节点3加入队列）
• 最终结果 result: [] （空列表）

第一轮大循环（处理第1层）：

• 当前队列长度 level_size = 1。
• 开始内层循环（循环1次）：
  • 从队列头部取出节点 3。
  • 将 3 的值加入临时列表 current_level: [3]。
  • 检查节点 3 的左右孩子：有左孩子 9 和右孩子 20。将它们按顺序加入队列尾部。现在队列变为：[9, 20]。
• 内层循环结束。将 current_level ([3]) 加入 result。现在 result = [[3]]。

第二轮大循环（处理第2层）：

• 当前队列长度 level_size = 2 （队列里有 9 和 20）。
• 开始内层循环（循环2次）：
  • 第一次内循环：
    • 取出节点 9。
    • 将 9 加入新的临时列表 current_level: [9]。
    • 检查节点 9 的左右孩子：没有（都是 null），所以不加入任何节点。队列变为：[20]。
  • 第二次内循环：
    • 取出节点 20。
    • 将 20 加入 current_level: [9, 20]。
    • 检查节点 20 的左右孩子：有左孩子 15 和右孩子 7。将它们加入队列尾部。队列变为：[15, 7]。
• 内层循环结束。将 current_level ([9, 20]) 加入 result。现在 result = [[3], [9,20]]。

第三轮大循环（处理第3层）：

• 当前队列长度 level_size = 2 （队列里有 15 和 7）。
• 开始内层循环（循环2次）：
  • 第一次内循环：
    • 取出节点 15。
    • 将 15 加入新的临时列表 current_level: [15]。
    • 检查节点 15 的左右孩子：没有，不操作。队列变为：[7]。
  • 第二次内循环：
    • 取出节点 7。
    • 将 7 加入 current_level: [15, 7]。
    • 检查节点 7 的左右孩子：没有，不操作。队列变为：[]（空）。
• 内层循环结束。将 current_level ([15, 7]) 加入 result。现在 result = [[3], [9,20], [15,7]]。

第四轮大循环：

• 队列为空，循环结束。

返回最终结果 result。

4. 代码实现（Python）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 初始化结果列表
        result = []
        
        # 如果根节点为空，直接返回空结果
        if not root:
            return result
        
        # 使用双端队列deque作为队列，比list的pop(0)效率高
        queue = deque([root])
        
        # 开始BFS循环
        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

代码关键点解释：

• from collections import deque：使用 deque 双端队列是因为在 Python 中，从列表 (list) 的头部弹出元素 (pop(0)) 的时间复杂度是 O(n)，而从 deque 的左侧弹出 (popleft()) 的时间复杂度是 O(1)，效率更高。
• while queue:：只要队列不为空，就继续遍历。
• level_size = len(queue)：这是区分不同层的关键。在开始处理一层之前，先固定住这一层的节点数量。
• for _ in range(level_size):：这个内层循环确保我们只处理当前层的 level_size 个节点。在这个过程中，我们可能会添加下一层的节点，但不会在当前循环中处理它们。

5. 复杂度分析

• 时间复杂度：O(n)。其中 n 是树中的节点数量。每个节点恰好会被放入队列一次，并从队列中取出一次，并进行常数级别的操作。
• 空间复杂度：O(n)。空间复杂度取决于队列的开销。在最坏情况下（平衡二叉树），队列中最多会存放约 n/2 个节点（即最后一层的节点数），因此是 O(n) 级别。

6. 总结与延伸

这道题是 BFS 在二叉树上的经典应用。掌握它对于解决以下问题至关重要：

• 变体问题：LeetCode 107（层序遍历 II，自底向上），LeetCode 103（锯齿形/之字形层序遍历）。
• 相关算法：图的 BFS 遍历算法思想与此完全一致。
• 实际问题：求树的最小高度、在树中寻找最短路径等。

希望这个从思路到代码，再到一步步演示的详细讲解，能让你彻底理解二叉树的层序遍历！如果还有任何疑问，随时可以提出。