LeetCode 102. 二叉树的层序遍历

题目描述

给你一个二叉树，请返回其节点值按 层序遍历 得到的序列（即逐层访问，从左到右访问所有节点）。

例如，给定二叉树：

    3
   / \
  9  20
    /  \
   15   7

层序遍历结果为：

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

解题过程

1. 理解层序遍历

层序遍历（BFS, Breadth-First Search）是一种按树的层次逐层访问节点的方法。其核心思想是：

• 先访问根节点（第0层）。
• 然后依次访问第1层的所有节点（从左到右）。
• 再访问第2层的所有节点，以此类推。

这种遍历方式天然适合使用 队列（Queue） 来实现。

2. 思路分析

常规的层序遍历（例如直接输出一维数组）只需一个队列即可：

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

但本题要求每一层的节点值分别放在一个子数组里，因此我们需要在遍历时知道当前节点属于哪一层。

3. 如何区分不同层？

两种常用方法：

方法一：在队列中记录层数
每个队列元素除了节点本身，还附带一个“层号”（或深度）。出队时，根据层号决定将节点值放入哪个子数组。

方法二：逐层处理
在一次循环中，先记录当前队列的长度 levelSize（即当前层的节点数），然后依次出队 levelSize 次，这些节点都属于同一层。每次出队时，将子节点入队（这些子节点属于下一层）。这样无需显式记录层号。

通常方法二更简洁，我们采用它。

4. 具体步骤

1. 初始化一个队列 queue，将根节点入队（如果根节点不为空）。
2. 初始化结果列表 result = []。
3. 当 queue 不为空时：
   • 获取当前队列长度 levelSize（当前层节点数）。
   • 初始化一个临时列表 levelVals = []，用于存放当前层的节点值。
   • 循环 levelSize 次：
     • 出队一个节点 node。
     • 将 node.val 加入 levelVals。
     • 如果 node 有左子节点，将左子节点入队。
     • 如果 node 有右子节点，将右子节点入队。
   • 将 levelVals 加入 result。
4. 返回 result。

5. 举例说明

以二叉树 [3,9,20,null,null,15,7] 为例：

初始：queue = [3]，result = []
第1层循环：
  levelSize = 1
  levelVals = []
  出队节点3，levelVals = [3]
  入队左右子节点9和20 → queue = [9,20]
  将levelVals加入result → result = [[3]]
第2层循环：
  levelSize = 2
  levelVals = []
  出队节点9，levelVals = [9]（无子节点）
  出队节点20，levelVals = [9,20]
  入队20的左右子节点15和7 → queue = [15,7]
  将levelVals加入result → result = [[3], [9,20]]
第3层循环：
  levelSize = 2
  levelVals = []
  出队节点15，levelVals = [15]（无子节点）
  出队节点7，levelVals = [15,7]（无子节点）
  队列变空
  将levelVals加入result → result = [[3], [9,20], [15,7]]
结束，返回result。

6. 代码实现（Python示例）

from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        levelVals = []
        levelSize = len(queue)
        
        for _ in range(levelSize):
            node = queue.popleft()
            levelVals.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(levelVals)
    
    return result

7. 复杂度分析

• 时间复杂度：O(N)，每个节点恰好入队、出队一次。
• 空间复杂度：O(N)，队列中最多存放一层的节点数，最坏情况下（完全二叉树底层）约为 N/2。