算法 - 二叉树的层序遍历 (BFS)

Posted on

1. 题目

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

示例:

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

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

节点定义同前（TreeNode）。

2. 解题思路

层序遍历 = 广度优先搜索（BFS），天然对应队列（先进先出）。

难点在于「如何把结果按层分开」。关键技巧：

每轮 while 开始时，队列里的元素恰好就是「当前层的全部节点」，数量为 queue.length。用 for (let i = 0; i = levelSize) 固定处理这一层，处理时把下一层的孩子依次入队。

流程：

  1. 根节点入队。
  2. 当队列非空：取 levelSize = queue.length，循环 levelSize 次，每次出队一个节点记录其值，并把它的左右孩子入队。
  3. 一层结束后，把这层的值数组 push 进结果。
  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)，队列最多容纳一层的节点（完全二叉树最后一层约 n/2）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function levelOrder(root: TreeNode | null): number[][] {
    if (root === null) return [];

    const res: number[][] = [];
    const queue: TreeNode[] = [root];

    while (queue.length > 0) {
        const levelSize = queue.length;
        const level: number[] = [];

        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            level.push(node.val);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }

        res.push(level);
    }

    return res;
}

性能提示：Array.shift() 是 O(n)，节点很多时可改用索引指针 head 模拟队列头，或直接用两个数组交替，避免频繁移动。面试手写版本用 shift 完全 OK。

4. 面试延伸

  • 锯齿形层序遍历（103 题）：偶数层反转 level，或双端队列两头取。
  • 自底向上层序（107 题）：正常 BFS 最后 res.reverse()。
  • 右视图（199 题）：每层只取最后一个节点值 level[levelSize - 1]。
  • 最小深度 / 最短路径类：BFS 求「层数」正是 [最大深度] 一文的 BFS 解法，也常用于网格最短步数。
  • 一句话记忆：BFS 用队列、DFS 用栈（或递归）；「按层」是 BFS 的标志。

难度：中等 | LeetCode 102 题 | BFS 模板题