太棒了！90分说明你的核心算法（BFS和锯齿遍历逻辑）已经完全正确，并且成功通过了从大规模随机数据到极端退化链状树的所有压力测试。

最后一个测试点（#1）报错 Runtime Error Aborted，这在 NOI 竞赛中是一个非常典型的“特例处理”问题。

1. 为什么 #1 报错？（病因分析）

在我的数据生成器里，Test #1 是一个空输入（Empty Tree）。

注意题目说了，树的节点数目大小范围在[0,2000]

报错的原因通常出在“辅助函数” buildTree 里，特别是当你使用 std::stoi 处理空字符串时。

请看你之前的辅助代码：

TreeNode* buildTree(string data) {
    if (data == "" || data == "null") return nullptr; // 如果输入完全为空，这里能过
    stringstream ss(data);
    string item;
    ss >> item; 
    TreeNode* root = new TreeNode(stoi(item)); // <--- 隐患在这里！
    // ...
}

报错逻辑推理：

1. 如果 OJ 的输入文件只有一个换行符，或者 getline 读到了一些不可见的空白字符。
2. ss >> item 可能失败，导致 item 为空。
3. std::stoi("") 会抛出一个 std::invalid_argument 异常。
4. 在没有任何 try-catch 的竞赛程序中，异常会导致程序直接 Aborted（崩溃退出），这就是你看到的 Runtime Error。

2. 修正方案：更健壮的“竞赛级”辅助函数

我们需要确保在调用 stoi 之前，字符串里确实有数字。

请尝试替换你的 buildTree 函数：

TreeNode* buildTree(string data) {
    // 1. 彻底过滤：如果字符串为空或者全是空白，直接返回空树
    if (data.empty()) return nullptr;

    stringstream ss(data);
    string item;
    
    // 2. 尝试读取第一个节点，如果读不到有效字符串，说明是空树
    if (!(ss >> item) || item == "null") {
        return nullptr;
    }

    // 3. 此时再调用 stoi 是安全的
    TreeNode* root = new TreeNode(stoi(item));
    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();

        // 处理左子节点
        if (!(ss >> item)) break;
        if (item != "null") {
            curr->left = new TreeNode(stoi(item));
            q.push(curr->left);
        }

        // 处理右子节点
        if (!(ss >> item)) break;
        if (item != "null") {
            curr->right = new TreeNode(stoi(item));
            q.push(curr->right);
        }
    }
    return root;
}

3. 教练的深度提醒：NOI 中的“安全编程”

在 NOI 考场上，这种“辅助代码导致的崩溃”比“算法写错”更令人惋惜。以下是三条保命建议：

1. 防御性编程：凡是涉及字符串转整数（stoi, atoi, sscanf），一定要确保字符串不为空且格式合法。
2. 避免 stoi 的陷阱：在有些老版本的竞赛编译器（如某些版本的 Dev-C++ 默认环境）中，stoi 甚至不在标准库里。建议练习使用 stringstream 配合 >> 运算符，它更慢一点点，但非常安全，不会抛异常：

   int val;
   stringstream ss(item);
   if (ss >> val) {
       // 读取成功
   }
   

3. 本地自测“空数据”： 在终端运行你的程序，直接按一次 Enter 再按 Ctrl+D（Linux/Mac）或 Ctrl+Z（Windows），模拟空输入。如果程序报 terminate called after throwing an instance of...，你就知道它在面对空输入时会崩溃。

4. 总结关键词

• Runtime Error (RE)：通常是溢出、除以零、或者未捕获的异常。
• Aborted：在 C++ 中极大概率是 throw 了异常（如 stoi 失败或 vector 越界访问 .at()）。

修改 buildTree 的读取判断逻辑后，再次提交，你就能拿到满分（100分）了！恭喜！

在 NOI 竞赛中，数据生成器（Generator）是检验算法正确性和准备比赛数据的核心工具。我们将编写一个名为 gen.cpp 的程序，它会自动生成 10 组测试数据（1.in ~ 10.in）并调用我们的“标准程序”生成对应的答案（1.out ~ 10.out）。

数据生成器设计思路

1. 覆盖边界条件：空树（N=0）、只有根节点（N=1）、完全二叉树、退化为链的树（极深）。
2. 树的构造：通过数组模拟法或随机连接法，确保生成的结构是一棵合法的二叉树。
3. 序列化：输出符合要求的 LeetCode 风格层序遍历字符串。
4. 非递归：生成器和解题逻辑均采用 BFS，避免递归导致的栈溢出。

C++ 数据生成器代码 (gen.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <ctime>
#include <cstdlib>

using namespace std;

// 定义树节点结构
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// --- [算法实现：标准解答逻辑] ---
vector<vector<int>> getZigzagLevelOrder(TreeNode* root) {
    if (!root) return {};
    vector<vector<int>> res;
    queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;
    while (!q.empty()) {
        int size = q.size();
        vector<int> level(size);
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();
            // 根据方向计算存放位置
            int index = leftToRight ? i : (size - 1 - i);
            level[index] = node->val;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
        leftToRight = !leftToRight;
    }
    return res;
}

// --- [序列化：树 -> 字符串] ---
string serialize(TreeNode* root) {
    if (!root) return "";
    string res = "";
    queue<TreeNode*> q;
    q.push(root);
    vector<string> nodes;
    
    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        if (curr) {
            nodes.push_back(to_string(curr->val));
            q.push(curr->left);
            q.push(curr->right);
        } else {
            nodes.push_back("null");
        }
    }
    // 去除末尾多余的 null
    while (!nodes.empty() && nodes.back() == "null") nodes.pop_back();
    for (int i = 0; i < nodes.size(); ++i) {
        res += nodes[i] + (i == nodes.size() - 1 ? "" : " ");
    }
    return res;
}

// --- [树生成逻辑] ---

// 1. 生成随机树
TreeNode* buildRandomTree(int n) {
    if (n <= 0) return nullptr;
    TreeNode* root = new TreeNode(rand() % 201 - 100);
    queue<TreeNode*> q;
    q.push(root);
    int count = 1;
    while (count < n && !q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        // 随机决定左孩子
        if (count < n && rand() % 10 < 8) { // 80%概率生成节点
            curr->left = new TreeNode(rand() % 201 - 100);
            q.push(curr->left);
            count++;
        }
        // 随机决定右孩子
        if (count < n && rand() % 10 < 8) {
            curr->right = new TreeNode(rand() % 201 - 100);
            q.push(curr->right);
            count++;
        }
    }
    return root;
}

// 2. 生成完全退化树（链状）
TreeNode* buildSkewedTree(int n, bool isLeft) {
    if (n <= 0) return nullptr;
    TreeNode* root = new TreeNode(rand() % 201 - 100);
    TreeNode* curr = root;
    for (int i = 1; i < n; ++i) {
        if (isLeft) {
            curr->left = new TreeNode(rand() % 201 - 100);
            curr = curr->left;
        } else {
            curr->right = new TreeNode(rand() % 201 - 100);
            curr = curr->right;
        }
    }
    return root;
}

// --- [主流程：生成测试点] ---
void make_test(int test_id, int n, string type) {
    string in_name = to_string(test_id) + ".in";
    string out_name = to_string(test_id) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);

    TreeNode* root = nullptr;
    if (type == "empty") root = nullptr;
    else if (type == "single") root = new TreeNode(rand() % 201 - 100);
    else if (type == "left_skewed") root = buildSkewedTree(n, true);
    else if (type == "right_skewed") root = buildSkewedTree(n, false);
    else root = buildRandomTree(n);

    // 写输入文件
    fin << serialize(root) << endl;

    // 写输出文件
    vector<vector<int>> res = getZigzagLevelOrder(root);
    for (const auto& level : res) {
        for (int i = 0; i < level.size(); ++i) {
            fout << level[i] << (i == level.size() - 1 ? "" : " ");
        }
        fout << endl;
    }

    cout << "Test " << test_id << " (" << type << ", n=" << n << ") generated." << endl;
    fin.close(); fout.close();
}

int main() {
    srand(time(0));
    
    // 测试点分布
    make_test(1, 0, "empty");           // 边界：空树
    make_test(2, 1, "single");          // 边界：单节点
    make_test(3, 10, "random");         // 小规模：随机
    make_test(4, 20, "left_skewed");    // 小规模：左链
    make_test(5, 20, "right_skewed");   // 小规模：右链
    make_test(6, 100, "random");        // 中规模
    make_test(7, 500, "random");        // 中规模
    make_test(8, 1000, "random");       // 大规模
    make_test(9, 2000, "random");       // 大规模（满额数据）
    make_test(10, 2000, "left_skewed"); // 大规模：深度最大化测试

    return 0;
}

数据说明与生成指南

1. 如何运行

1. 将上述代码保存为 gen.cpp。
2. 使用命令编译：g++ -std=c++14 gen.cpp -o gen。
3. 运行 ./gen，当前目录下会生成 1.in ~ 10.in 和 1.out ~ 10.out。

2. 测试点规模设计思路

• Test 1 & 2: 确保程序能处理最极端的情况而不崩溃。
• Test 4 & 5: 链状树测试 BFS 的深度处理能力。
• Test 9: 节点数达到题目上限 2000。在这种情况下，BFS 的 queue 最多存储 1000 个节点，内存消耗极低。
• Test 10: 最大深度测试。有些不成熟的递归解法可能会在深度 2000 时在 Windows 环境下爆栈（默认栈较小），此数据可区分递归与迭代。

3. 性能与大小优化

• 文件大小：由于 $N \le 2000$，即使每个节点值 4 字节加上 null 占位，单个 .in 文件大小约在 15-20 KB 左右。10 组数据总大小远小于 2MB，非常适合 OJ 快速上传和测评。
• 时间复杂度：生成器的复杂度为 $O(N)$，构建 10 组数据总共耗时不到 0.1 秒。
• 异常处理：
  • 除零：本题不涉及除法。
  • 内存：通过 new 创建节点。对于 2000 个节点的规模，不需要手动 delete 释放，进程结束时操作系统会自动回收。
  • 栈空间：getZigzagLevelOrder 采用了 std::queue 的迭代写法，serialize 亦然，完全规避了深度带来的爆栈风险。

4. 读题关键词总结

• 层序 (Level)：提示必须按层扫描，通常使用 BFS。
• 锯齿 (Zigzag)：提示需要根据层数的单双数来改变存入结果数组的顺序。
• null：这是输入序列化的关键，理解 null 代表空指针是解析输入数据的核心。

举例讲解一下这里二叉树节点的结构体声明方法，特别是构造函数写法

在 NOI 竞赛中，虽然我们有时会为了效率使用静态数组来模拟树，但理解 结构体（struct） 及其 构造函数（Constructor） 是掌握 C++ 面向对象编程和动态内存管理的基础。

这几行代码是 C++ 经典的“链式二叉树”节点定义。我们分层来拆解：

1. 结构体成员 (Data Members)

struct TreeNode {
    int val;            // 存储节点的值
    TreeNode *left;     // 指向左子节点的指针
    TreeNode *right;    // 指向右子节点的指针
};

• 为什么用 struct 而不是 class？ 在竞赛中，struct 的成员默认是 public（公开）的，这意味着你可以直接通过 node->left 访问成员。这比 class 需要写 get/set 方法快得多。
• 自引用指针：left 和 right 的类型是 TreeNode*，因为它们指向的是另一个同类型的结构体。

2. 构造函数 (Constructor)

这就是你提到的重点部分：

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

A. 什么是构造函数？

当你执行 new TreeNode(5) 时，系统会自动调用这个函数。它的名字必须与结构体名称完全一致，且没有返回值类型（连 void 都没有）。

B. 初始化列表 (Initialization List) —— 重点

冒号 : 后面、大括号 {} 前面的部分叫做初始化列表。

• 语法格式：变量名(初始值), 变量名(初始值)
• 这里的含义：
  1. val(x)：把传入的参数 x 赋值给成员变量 val。
  2. left(nullptr)：把左孩子指针初始化为空（C++14 标准建议使用 nullptr 而非 NULL）。
  3. right(nullptr)：把右孩子指针初始化为空。

C. 为什么不写在大括号里面？

你可能会问，为什么不写成下面这样？

// 虽然可行，但不推荐的写法
TreeNode(int x) {
    val = x;
    left = nullptr;
    right = nullptr;
}

原因有两点：

1. 效率更高：初始化列表是“在变量出生时就赋予初值”；而写在大括号里是“变量先出生（被默认初始化），然后被擦除再赋新值”。在处理复杂对象时，初始化列表能省去一次构造开销。
2. 竞赛风格：这种写法非常简洁，能在一行内完成所有初始化工作。

3. 如何在代码中使用它？

在 NOI 竞赛中，使用这个构造函数通常有两种方式：

方式一：动态申请内存（适合 LeetCode 或 节点数不确定的题）

// 在堆内存中创建一个值为 10 的节点
TreeNode* node = new TreeNode(10); 

// 访问成员
cout << node->val;   // 输出 10
cout << node->left;  // 输出 0 (nullptr)

方式二：局部变量（适合递归内部临时创建）

TreeNode tempNode(5); // 在栈内存创建
// 访问成员用 . 符号
cout << tempNode.val; 

4. 【NOI 竞赛提点】静态数组模拟 vs 指针结构

在 NOI 考场上，如果题目给出了明确的节点总数 $N$（如 $N \le 10^5$），教练通常推荐使用静态数组来代替 new 操作。

为什么？

• new 操作在大量调用时比较慢。
• 指针占用空间较大（64位系统下占 8 字节）。
• 容易产生内存泄漏。

静态数组版的结构体写法：

const int MAXN = 100005;
struct Node {
    int val;
    int l, r; // 存储左右孩子的下标，而不是指针
} tree[MAXN];

// 初始化
void init(int i, int x) {
    tree[i].val = x;
    tree[i].l = -1; // -1 代表空
    tree[i].r = -1;
}

总结： 原题中的那种写法是标准 C++ 的二叉树链式表示法。

• val(x) 是赋初值。
• left(nullptr) 是为了防止“野指针”（即指针指向了随机的内存地址，导致程序崩溃）。
• 大括号 {} 为空是因为所有的初始化工作已经在冒号后面做完了。

在 NOI/NOIP 竞赛中，我们不仅追求“写出答案”，更追求代码的稳定性、空间利用率以及在极端数据下的表现。

以下是该题目的两个版本：从最符合直觉的“暴力翻转版”到更精细的“双端队列/预分配版”。

版本一：基础 BFS + 逻辑翻转（最推荐，竞赛中最稳）

思路思考： 这是最容易实现的方案。先不考虑锯齿形，直接用 std::queue 做标准层序遍历。在每一层处理完后，根据当前层数的奇偶性，使用 std::reverse 翻转该层结果。

时间复杂度分析：

• 每个节点入队出队各一次：$O(N)$。
• 虽然有翻转操作，但每一层翻转的代价之和等于节点总数 $N$：$O(N)$。
• 总时间复杂度：$O(N)$。

空间复杂度分析：

• 队列存储一层的节点，最坏情况（完全二叉树底层）为 $O(N)$。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

// NOI 竞赛风格：定义树节点
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/**
 * 版本一：BFS + std::reverse
 * 优点：代码逻辑极其简单，不容易在考场上写挂。
 * 易错点：注意处理 root 为空的情况；注意层数从 0 开始还是 1 开始。
 */
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if (!root) return {}; // 易错点：处理空树

    vector<vector<int>> res;
    queue<TreeNode*> q;
    q.push(root);

    bool leftToRight = true; // 标志位：控制方向

    while (!q.empty()) {
        int size = q.size();
        vector<int> level;

        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();

            level.push_back(node->val);
            // 标准 BFS 始终左子在前，右子在后入队
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        // 关键逻辑：如果是偶数层（从0开始计），则翻转
        if (!leftToRight) {
            reverse(level.begin(), level.end());
        }
        res.push_back(level);
        leftToRight = !leftToRight; // 切换方向
    }
    return res;
}

// 辅助函数：根据层序序列构建树（用于 main 运行测试）
TreeNode* buildTree(string data) {
    if (data == "" || data == "null") return nullptr;
    stringstream ss(data);
    string item;
    ss >> item;
    TreeNode* root = new TreeNode(stoi(item));
    queue<TreeNode*> q;
    q.push(root);
    while (ss >> item) {
        TreeNode* curr = q.front(); q.pop();
        if (item != "null") {
            curr->left = new TreeNode(stoi(item));
            q.push(curr->left);
        }
        if (!(ss >> item)) break;
        if (item != "null") {
            curr->right = new TreeNode(stoi(item));
            q.push(curr->right);
        }
    }
    return root;
}

int main() {
    // 1. 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    // 2. 从标准输入读取一整行数据（适配 OJ 测评环境）
    if (getline(cin, line) && !line.empty()) {
        TreeNode* root = buildTree(line);
        vector<vector<int>> result = zigzagLevelOrder(root);

        // 3. 规范输出
        for (const auto& row : result) {
            for (size_t i = 0; i < row.size(); ++i) { // 使用 size_t 解决图片中的 Warning
                cout << row[i] << (i == row.size() - 1 ? "" : " ");
            }
            cout << "\n"; // 竞赛建议使用 "\n" 代替 endl 提高速度
        }
    }

    return 0;
}

版本二：双端队列 + 内存预分配（最优常数优化）

思路思考： 在版本一中，reverse 操作和 vector 的频繁动态扩容（push_back）在极端大数据下会有常数开销。我们可以通过 std::deque 动态调整插入位置，或者直接申请固定大小的 vector 并利用下标填值。

优化策略：

• 使用 deque：如果从左往右，push_back；如果从右往左，push_front。
• 这种方法避免了 reverse 操作，理论常数更小。

时间/空间复杂度：

• 与版本一一致，$O(N)$。

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <string>
#include <sstream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

/**
 * 版本二：利用 deque 的双端插入特性
 * 提示：在 NOI 中，若对空间及其敏感，可手动分配数组模拟 deque
 */
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    if (!root) return {};

    vector<vector<int>> res;
    queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;

    while (!q.empty()) {
        int size = q.size();
        // 使用 deque 存储当前层结果，支持两端高效插入
        deque<int> levelNodes;

        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.front();
            q.pop();

            if (leftToRight) {
                levelNodes.push_back(node->val);
            } else {
                levelNodes.push_front(node->val); // 核心优化：直接头插
            }

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        // 将 deque 转换为 vector 存入结果集
        res.emplace_back(levelNodes.begin(), levelNodes.end());
        leftToRight = !leftToRight;
    }
    return res;
}

// buildTree 与 main 函数同上
// 辅助函数：根据层序序列构建树（用于 main 运行测试）
TreeNode* buildTree(string data) {
    if (data == "" || data == "null") return nullptr;
    stringstream ss(data);
    string item;
    ss >> item;
    TreeNode* root = new TreeNode(stoi(item));
    queue<TreeNode*> q;
    q.push(root);
    while (ss >> item) {
        TreeNode* curr = q.front(); q.pop();
        if (item != "null") {
            curr->left = new TreeNode(stoi(item));
            q.push(curr->left);
        }
        if (!(ss >> item)) break;
        if (item != "null") {
            curr->right = new TreeNode(stoi(item));
            q.push(curr->right);
        }
    }
    return root;
}

int main() {
    // 1. 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    // 2. 从标准输入读取一整行数据（适配 OJ 测评环境）
    if (getline(cin, line) && !line.empty()) {
        TreeNode* root = buildTree(line);
        vector<vector<int>> result = zigzagLevelOrder(root);

        // 3. 规范输出
        for (const auto& row : result) {
            for (size_t i = 0; i < row.size(); ++i) { // 使用 size_t 解决图片中的 Warning
                cout << row[i] << (i == row.size() - 1 ? "" : " ");
            }
            cout << "\n"; // 竞赛建议使用 "\n" 代替 endl 提高速度
        }
    }

    return 0;
}

六、 复杂度分析思考过程

1. 时间分析：

   • 层序遍历本质是 BFS。在 BFS 中，每个节点必须且只能进入队列一次，出队列一次。
   • 对每个节点的处理（判断子节点、存入临时数组）都是 $O(1)$ 的。
   • 总代价为 $O(1) \times N = O(N)$。
   • 优化建议：在 C++ 中，vector::push_back 是均摊 $O(1)$。如果已知树的宽度，可以使用 vector::reserve 预分配内存，减少重分配开销。

2. 空间分析：

   • 队列空间：最坏情况下（例如一棵满二叉树），最后一层有 $N/2$ 个节点，因此 std::queue 最大会占用 $O(N)$ 空间。
   • 结果空间：返回的二维数组必然占用 $O(N)$ 空间（不计入算法额外空间消耗时通常忽略，但在 NOI 空间限制严格时需留意）。

七、 总结：读题关键词与易错点

1. 关键词：

   • “Binary Tree”：确定数据结构。
   • “Level Order”：锁定 BFS 算法。
   • “Zigzag”：暗示需要一个状态位（bool）或判断层数（depth % 2）来决定处理顺序。
   • “Return values”：注意返回值格式（二维数组）。

2. NOI 竞赛常见陷阱：

   • 空树判断：if (!root) 必须写在最前面，否则 q.push(root) 后续逻辑可能崩溃。
   • 层大小固定：在 while 循环内部，必须先取 int size = q.size();。不能直接在 for 循环里写 i < q.size()，因为循环中 q.size() 是在变化的。
   • 内存管理：在正式比赛中，如果题目给定了节点总数，使用静态数组模拟二叉树（tree[i].left = l）通常比 new 动态开辟内存更快且更安全。

3. 时间复杂度优化建议：

   • 虽然 $O(N)$ 已经是最优，但可以通过 std::deque 或手动翻转来减小常数。
   • 在内存受限时，可以使用 DFS 配合深度标记来实现层序遍历，空间复杂度可降至 $O(H)$，$H$ 为树高。