你好，同学！很高兴你能挑战这道经典的二叉树题目。在 NOI 竞赛中，树的遍历是基础中的基础，而“变体遍历”则是考查你对数据结构（如队列、双端队列、栈）灵活运用能力的绝佳机会。

下面我将从竞赛教练的角度，为你剖析这道题。

一、 题目描述 (NOI 格式)

题目名称： 二叉树的锯齿形层序遍历 (Binary Tree Zigzag Level Order Traversal) 时间限制： 1.0s 内存限制： 256MB

【问题描述】 给定一棵二叉树的根节点 root，请你返回其值的 锯齿形层序遍历。 即：第一层从左向右遍历，第二层从右向左遍历，第三层再从左向右遍历，以此类推，在相邻层之间交替改变遍历的方向。

【输入格式】 输入文件包含一棵二叉树。由于是模拟竞赛环境，我们约定输入采用类似于完全二叉树的序列化表达（空节点用 null 表示，但在代码实现中你将直接面对题目提供的类定义结构）。

【输出格式】 输出一个二维数组，每一行代表树的一层。

【样例 1 输入】

3 9 20 null null 15 7

【样例 1 输出】

3
20 9
15 7

【数据范围】

• 树中节点数目在 $[0, 2000]$ 范围内。
• $-100 \le Node.val \le 100$

二、 预备知识点

在动手之前，请确保你已经熟练掌握以下内容：

1. 二叉树基础：了解 left, right 指针结构。
2. BFS (广度优先搜索)：掌握使用 std::queue 进行层序遍历的标准模板。
3. 双端队列 (Deque) 或 Vector 翻转：理解如何高效地在两端插入数据或局部逆序。
4. STL 容器操作：std::vector 的动态扩容与遍历。

三、 启发式思路引导：草稿纸上的推理

现在，请拿出你的草稿纸，跟我一起画图：

第一步：回归本质

忽略“锯齿形”，如果这只是普通的层序遍历，你会怎么做？

• 动作：使用一个队列 q，先把根节点入队。
• 循环：每次记录当前队列的大小 size（即这一层的节点数），然后弹出一个、处理一个、将其左右子节点入队。
• 结果：你得到了每一层从左到右的结果。

第二步：引入“锯齿”规律

观察样例，思考方向切换的逻辑：

• 第 0 层（根）：左 $\to$ 右 (3)
• 第 1 层：右 $\to$ 左 (20, 9)
• 第 2 层：左 $\to$ 右 (15, 7)
• 结论：当 层数 % 2 != 0 时，我们需要倒序存储该层结果。

第三步：选择最优数据结构

在草稿纸上模拟两种实现方案：

1. 方案 A (后处理法)：依然按从左到右存入 vector，最后判断如果是奇数层，调用 std::reverse。
2. 方案 B (双端队列法)：在存入每一层结果时，如果是奇数层，始终从头部插入（push_front）；如果是偶数层，从尾部插入（push_back）。

第四步：复杂度分析

• 时间复杂度：每个节点仅访问一次，如果是翻转操作，总翻转元素个数也是 $N$，故为 $O(N)$。
• 空间复杂度：需要一个队列存储节点，最大宽度出现在最底层，最坏情况下为 $O(N)$。

四、 算法流程图 (伪代码提示)

为了避免 Mermaid 渲染错误，特殊符号已进行处理。

graph TD
    A("开始: zigzagLevelOrder(root)") --> B{"root == null?"}
    B -- "是" --> C("返回空结果")
    B -- "否" --> D("初始化 Queue q, 将 root 入队")
    D --> E("bool isOrderLeft = true")
    E --> F{"Queue 是否为空?"}
    F -- "否" --> G("获取当前层 size")
    G --> H("创建临时容器 resLevel 存储当前层")
    H --> I("循环执行 size 次")
    I --> J("从 q 弹出节点 node")
    J --> K{"isOrderLeft 为真?"}
    K -- "是" --> L("将 node.val 放入 resLevel 尾部")
    K -- "否" --> M("将 node.val 放入 resLevel 头部")
    L --> N("node 的左右子节点若存在则入队 q")
    M --> N
    N --> O("循环结束?")
    O -- "否" --> I
    O -- "是" --> P("将 resLevel 加入总结果 ans")
    P --> Q("isOrderLeft 取反")
    Q --> F
    F -- "是" --> R("返回 ans")

五、 竞赛技巧：如何读懂题意关键点

在 NOI 考场上，读题时要敏锐捕捉以下关键词：

1. “层序” (Level Order)：

   • 直觉反应：必须用 BFS。
   • 代码套路：while(!q.empty()) { int sz = q.size(); ... }。

2. “锯齿形/交替” (Zigzag/Alternate)：

   • 直觉反应：需要一个 bool 变量或 depth 计数器来控制方向。
   • 处理细节：方向切换是发生在“每一层处理完后”还是“处理每个节点时”？（本题是层与层之间切换）。

3. 数据范围 $[0, 2000]$：

   • 直觉反应：数据量极小。$O(N)$ 或 $O(N \log N)$ 都能轻松过。这意味着你可以放心使用 std::reverse 或 std::deque，不用担心常数开销。

4. 空节点处理：

   • 注意：树可能为空（根节点为 null）。在 NOI 中，一定要考虑 $N=0$ 的特例，否则可能会发生非法指针访问（段错误/RE）。

加油，少年！尝试用 std::deque 来优化你的空间操作吧！