概述#

层序遍历是二叉树上的 BFS。它按层从上到下、从左到右访问节点，非常适合处理“每一层”的问题。

与递归 DFS 不同，层序遍历使用队列维护当前待访问节点。队列先进先出的特性，刚好对应树的层级顺序。

常见变体包括：每层节点列表、锯齿形遍历、右视图、每层最大值、每层平均值。

前置知识

• 二叉树：层序遍历按深度访问节点
• 队列：先进先出保证同层顺序
• BFS：层序遍历是树上的广度优先搜索

问题定义#

给定二叉树：

1
      3
2
     / \
3
    9   20
4
       /  \
5
      15   7

层序遍历结果是：

1
[
2
  [3],
3
  [9, 20],
4
  [15, 7]
5
]

问题的关键是：如何知道当前层有多少个节点？

答案是：在处理每一层之前，先记录队列当前长度。这个长度就是当前层节点数。

核心原理：分步图解#

初始时，队列只有根节点：

1
queue: [3]

处理第 1 层，弹出 3，把子节点加入队列：

1
result: [[3]]
2
queue: [9, 20]

处理第 2 层时，先记录 levelSize = 2，只处理这两个节点。它们产生的子节点属于下一层：

1
result: [[3], [9, 20]]
2
queue: [15, 7]

队列天然保证了从上到下的顺序，而 levelSize 划定了每一层的边界。

算法精细步骤#

标准层序遍历：

1. 如果根节点为空，返回空数组；
2. 将根节点入队；
3. 当队列不为空时，记录当前队列长度；
4. 循环处理当前层的所有节点；
5. 弹出节点，记录值；
6. 将它的非空左右子节点入队；
7. 当前层处理完成后，把层结果加入答案。

复杂度：

• 时间复杂度 O(n)，每个节点入队出队一次；
• 空间复杂度 O(w)，w 是树的最大宽度。

TypeScript 实现#

1
class TreeNode<T> {
2
  constructor(
3
    public value: T,
4
    public left: TreeNode<T> | null = null,
5
    public right: TreeNode<T> | null = null,
6
  ) {}
7
}

1
function levelOrder<T>(root: TreeNode<T> | null): T[][] {
2
  if (root === null) return [];
3

4
  const result: T[][] = [];
5
  const queue: TreeNode<T>[] = [root];
6
  let head = 0;
7

8
  while (head < queue.length) {
9
    const levelSize = queue.length - head;
10
    const level: T[] = [];
11

12
    for (let i = 0; i < levelSize; i++) {
13
      const node = queue[head++];
14
      level.push(node.value);
15

16
      if (node.left) queue.push(node.left);
17
      if (node.right) queue.push(node.right);
18
    }
19

20
    result.push(level);
21
  }
22

23
  return result;
24
}

1
function rightSideView<T>(root: TreeNode<T> | null): T[] {
2
  return levelOrder(root).map(level => level[level.length - 1]);
3
}

1
function zigzagLevelOrder<T>(root: TreeNode<T> | null): T[][] {
2
  const levels = levelOrder(root);
3

4
  for (let i = 1; i < levels.length; i += 2) {
5
    levels[i].reverse();
6
  }
7

8
  return levels;
9
}

工程优化：队列不要频繁 shift#

很多示例会这样写：

1
const node = queue.shift();

这在小数据下没问题，但 shift 会移动数组元素，频繁调用可能带来 O(n) 成本。更稳妥的方式是使用 head 指针：

1
const node = queue[head++];

这种方式把队列出队变成 O(1)，特别适合节点数量较大的树或图。

应用与局限#

总结#

graph LR
    A[根节点入队] --> B[处理当前层]
    B --> C[子节点入队]
    C --> D[进入下一层]

• 层序遍历是二叉树上的 BFS。
• 队列保证访问顺序，levelSize 划分层边界。
• 每个节点只入队出队一次，时间复杂度 O(n)。
• 用头指针替代 shift 能避免数组搬移成本。
• 层序遍历适合所有“按层统计或观察”的问题。