二叉树的层序遍历（LeetCode 第 102 题）

题目描述：
给你一个二叉树的根节点 root，返回其节点值的层序遍历结果。即逐层地，从左到右访问所有节点，需要以二维列表的形式返回遍历结果，其中每个子列表代表一层中的节点值。

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

解题过程：

1. 理解层序遍历：
   层序遍历（Level Order Traversal）是一种广度优先搜索（BFS）策略。与深度优先搜索（DFS）不同，BFS 会先访问离根节点最近的节点，然后逐层向下。这意味着我们需要按层级顺序处理节点：先处理根节点（第 0 层），然后是根节点的左右子节点（第 1 层），接着是第 1 层节点的子节点（第 2 层），以此类推。

2. 核心思路：
   层序遍历通常借助队列（Queue）来实现。队列是一种先进先出（FIFO）的数据结构，非常适合处理按顺序访问的需求。基本步骤是：

   • 将根节点入队。
   • 当队列不为空时，循环处理：
     a. 记录当前队列的大小（即当前层的节点数）。
     b. 依次出队当前层的所有节点，并将它们的值存入一个临时列表。
     c. 将每个出队节点的非空左右子节点入队。
   • 将临时列表加入结果列表，代表一层遍历完成。

3. 详细步骤：

   • 初始化：创建一个结果列表 result 和一个队列 queue。如果根节点不为空，将根节点入队。
   • 循环处理队列：
     • 每次循环开始前，先获取当前队列的大小 size，这表示当前层的节点数量。
     • 创建一个空列表 level，用于存储当前层的节点值。
     • 循环 size 次：
       • 从队列中出队一个节点。
       • 将该节点的值加入 level 列表。
       • 如果该节点有左子节点，将左子节点入队。
       • 如果该节点有右子节点，将右子节点入队。
     • 将 level 列表添加到 result 中。
   • 当队列为空时，所有层都已处理完毕，返回 result。

4. 示例演示：
   以 root = [3,9,20,null,null,15,7] 为例：

   • 初始化：queue = [3], result = []。
   • 第 0 层（size=1）：
     • 出队节点 3，level = [3]。
     • 入队节点 3 的左子节点 9 和右子节点 20，queue = [9,20]。
     • 将 level 加入 result，result = [[3]]。
   • 第 1 层（size=2）：
     • 出队节点 9，level = [9]；入队其子节点（无），queue = [20]。
     • 出队节点 20，level = [9,20]；入队其左子节点 15 和右子节点 7，queue = [15,7]。
     • 将 level 加入 result，result = [[3],[9,20]]。
   • 第 2 层（size=2）：
     • 出队节点 15，level = [15]；入队其子节点（无），queue = [7]。
     • 出队节点 7，level = [15,7]；入队其子节点（无），queue = []。
     • 将 level 加入 result，result = [[3],[9,20],[15,7]]。
   • 队列为空，返回 result。

5. 复杂度分析：

   • 时间复杂度：O(n)，其中 n 是二叉树中的节点数。每个节点恰好被访问一次。
   • 空间复杂度：O(n)，队列中最多存储一层的节点数，最坏情况下（完美二叉树）最后一层约有 n/2 个节点。

6. 代码实现（Python）：

from collections import deque

def levelOrder(root):
    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

通过以上步骤，你可以清晰地理解层序遍历的工作原理和实现方法。这种算法是处理树结构问题的基础，也是许多高级算法（如求树的高度、宽度等）的基石。