算法 - 二叉树的锯齿形层序遍历

Posted on

1. 题目

给你二叉树的根节点 root，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例:

1
2
3
4
5
6
7
8
输入: root = [3,9,20,null,null,15,7]
        3
       / \
      9  20
     /  \
    15   7
输出: [[3],[20,9],[15,7]]
解释: 第 0 层从左到右 [3]，第 1 层从右到左 [20,9]，第 2 层从左到右 [15,7]。

2. 解题思路

本质还是层序遍历（BFS），只是在收集结果时按层的奇偶决定正序还是逆序。

2.1 BFS + 奇偶翻转（推荐）

  • 用队列逐层遍历，逻辑与普通层序遍历完全一致。

  • 维护 leftToRight 布尔标记，每处理完一层取反。

  • 该层节点值先按正常顺序存入 level，若当前层应从右到左，则 level.reverse() 后再 push 进结果。

  • 时间复杂度：O(n)，空间复杂度：O(n)。

2.2 双端队列 / 头尾插入

把每层结果用 unshift/push 分别从头或尾插入，避免整层 reverse。写法更巧但可读性略差。

3. TypeScript 实现

3.1 BFS + 层反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val = 0) {
        this.val = val;
        this.left = this.right = null;
    }
}

function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if (!root) return [];
    const res: number[][] = [];
    const queue: TreeNode[] = [root];
    let leftToRight = true;

    while (queue.length) {
        const size = queue.length;
        const level: number[] = [];

        for (let i = 0; i < size; 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(leftToRight ? level : level.reverse());
        leftToRight = !leftToRight; // 下一层方向翻转
    }

    return res;
}

3.2 头尾插入（免 reverse）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function zigzagLevelOrderDeque(root: TreeNode | null): number[][] {
    if (!root) return [];
    const res: number[][] = [];
    let queue: TreeNode[] = [root];
    let leftToRight = true;

    while (queue.length) {
        const level: number[] = [];
        const next: TreeNode[] = [];

        for (const node of queue) {
            leftToRight ? level.push(node.val) : level.unshift(node.val);
            if (node.left) next.push(node.left);
            if (node.right) next.push(node.right);
        }

        res.push(level);
        queue = next;
        leftToRight = !leftToRight;
    }

    return res;
}

4. 面试延伸

  • 与二叉树层序遍历、右视图是同一套 BFS 模板的小变形，考察「层」的边界控制（size 快照）。
  • DFS 也能做：把每层值按奇偶 push/unshift 到 res[depth]，注意方向由 depth % 2 决定。
  • 坑点：level.reverse() 是原地反转，此处无副作用；但在其他共享引用场景要警惕。

难度：中等 | LeetCode 103 | BFS 层序变形