二叉树的锯齿形层序遍历 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

节点数目在 [0, 2000] 内，节点值在 [-100, 100] 范围内。

示例 1

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

输出：[[3],[20,9],[15,7]]

示例 2

输入：root = [1]

输出：[[1]]

示例 3

输入：root = []

输出：[]

💭 模拟答题者思考

1. 暴力直觉：先按 #102 做普通层序得到 [[3],[9,20],[15,7]]，再对第 1、3、5… 层（0-based 下标为奇数）反转内层数组——正确且好写，多一次 O(宽度) 反转，总仍 O(n)。

2. 重复在哪里？锯齿形与普通层序的 BFS 骨架完全一样：队列、按层 size 分批、孩子左→右入队；唯一差别是「这一层写入答案的顺序」。

3. 关键技巧：不要在入队时交替「先右后左」——那样会破坏下一层 BFS 的发现顺序；应在收集完本层 level 后，根据层号决定是否 reverse，或双端队列按方向头/尾插入（等价思路）。

4. 示例 1：层 0 [3] 不变；层 1 收集 [9,20] 反转为 [20,9]；层 2 [15,7] 不变 → [[3],[20,9],[15,7]]。

5. 每个节点仍只入队出队一次，时间 O(n)；空间 O(n)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`q`	deque<TreeNode*>	定义：BFS 队列，与 #102 相同，孩子始终按左→右入队以保证「同层从左到右被发现」维护：每轮处理固定 `size` 个节点，对应当前层更新：弹出节点后将其非空子节点依次入队
`level`	list<int>	定义：当前层按 BFS 顺序收集到的节点值（总是从左到右）维护：一轮 `size` 次弹出内依次 `append(node.val)` 更新：写入 `ans` 前若当前层需「从右往左」展示，则对 `level` 做 `reverse`
`left_to_right`	bool	定义：本层写入答案时是否保持左→右（根层为 `true`）维护：奇数层（0-based 的 1、3、5…）为 `false`，需反转 `level` 更新：每处理完一层执行 `left_to_right = not left_to_right`
`ans`	list<list<int>>	定义：锯齿形层序结果，外层为层号维护：每层一个内层数组，方向由 `left_to_right` 决定更新：`ans.append(level)` 或 `ans.append(level[::-1])` 的等价写法

⌨️ 落码步骤

1. 若 root 为空，返回 []

2. ans = []，q = deque([root])，left_to_right = True

3. 当队列非空：新建 level = []，size = len(q)

4. 循环 size 次弹出节点，收集 val，非空子节点按左→右入队

5. 若 not left_to_right，level.reverse()；ans.append(level)；left_to_right = not left_to_right

6. 返回 ans

💻 代码实现

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: TreeNode | None) -> list[list[int]]:
        if not root:
            return []
        ans: list[list[int]] = []
        q: deque[TreeNode] = deque([root])
        left_to_right = True
        while q:
            level: list[int] = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if not left_to_right:
                level.reverse()
            ans.append(level)
            left_to_right = not left_to_right
        return ans

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        bool leftToRight = true;
        while (!q.empty()) {
            int size = (int)q.size();
            vector<int> level;
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (!leftToRight) reverse(level.begin(), level.end());
            ans.push_back(std::move(level));
            leftToRight = !leftToRight;
        }
        return ans;
    }
};
// 时间 O(n)，空间 O(n)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)（队列最坏存满一层，约 n/2 个节点）

⚠️ 常见坑

❗ 在奇数层把子节点「先右后左」入队：当前层可能看似对了，但下一层 BFS 顺序已乱，锯齿形会全错。

❗ 层号从 1 还是从 0 数错：题意根层从左到右，应对 0-based 的偶数层不反转、奇数层反转（或用 left_to_right 初值 true 每层翻转）。

❗ 忘记按层 size 分批：与 #102 相同，会把多层混在一行里。

🔍 必测边界 Case

Case 1：空树

root = [] → []

Case 2：单节点

root = [1] → [[1]]（仅一层，无需反转）

Case 3：官方示例 1

root = [3,9,20,null,null,15,7] → [[3],[20,9],[15,7]]

Case 4：两层满二叉

root = [1,2,3] → [[1],[3,2]]（第二层从右到左）