作为教练，我为你准备了一个标准、高效且防爆栈的数据生成器。它不仅能生成符合 NOI 规范的输入文件（.in），还能利用非递归 BFS 算法自动生成对应的标准答案（.out）。

为了确保数据文件精简且具有区分度，我将节点规模设定在 $N=1000$ 以内（本题逻辑简单，$O(N)$ 即可过关，文件大小将远小于 2MB），并涵盖了所有关键的边界情况。

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

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <algorithm>
#include <random>
#include <string>

using namespace std;

// 节点结构体
struct Node {
    int val;
    int l, r;
};

// ---------------------------------------------------------
// 核心：非递归 BFS 求解并写入答案
// ---------------------------------------------------------
void solve_and_write(int n, vector<Node> tree, string out_name) {
    ofstream fout(out_name);
    if (n <= 0) {
        fout.close();
        return;
    }

    // 1. 翻转逻辑：非递归遍历所有节点交换左右孩子
    for (int i = 0; i < n; ++i) {
        swap(tree[i].l, tree[i].r);
    }

    // 2. 层序遍历输出结果
    queue<int> q;
    q.push(0); // 根节点固定为 0
    bool first = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (!first) fout << " ";
        fout << tree[u].val;
        first = false;

        if (tree[u].l != -1) q.push(tree[u].l);
        if (tree[u].r != -1) q.push(tree[u].r);
    }
    fout << endl;
    fout.close();
}

// ---------------------------------------------------------
// 各种形态的树生成函数
// ---------------------------------------------------------
void make_tree(int id, int n, int type) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fin(in_name);

    if (n == 0) {
        fin << 0 << endl;
        fin.close();
        solve_and_write(0, {}, out_name);
        return;
    }

    vector<Node> tree(n, {0, -1, -1});
    mt19937 rng(id + 2025);
    uniform_int_distribution<int> val_dist(-100, 100);

    for (int i = 0; i < n; ++i) tree[i].val = val_dist(rng);

    if (type == 1) { // 极端左斜链
        for (int i = 0; i < n - 1; ++i) tree[i].l = i + 1;
    } 
    else if (type == 2) { // 极端右斜链
        for (int i = 0; i < n - 1; ++i) tree[i].r = i + 1;
    }
    else if (type == 3) { // 满二叉树结构
        for (int i = 0; i < n; ++i) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n) tree[i].l = left;
            if (right < n) tree[i].r = right;
        }
    }
    else { // 随机二叉树 (保证连通)
        vector<int> nodes(n);
        for(int i=0; i<n; ++i) nodes[i] = i;
        // 随机父节点分配
        for (int i = 1; i < n; ++i) {
            int p = uniform_int_distribution<int>(0, i - 1)(rng);
            while (tree[p].l != -1 && tree[p].r != -1) {
                p = uniform_int_distribution<int>(0, i - 1)(rng);
            }
            if (tree[p].l == -1 && tree[p].r == -1) {
                if (rng() % 2) tree[p].l = i; else tree[p].r = i;
            } else if (tree[p].l == -1) {
                tree[p].l = i;
            } else {
                tree[p].r = i;
            }
        }
    }

    // 写入输入文件
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << tree[i].val << " " << tree[i].l << " " << tree[i].r << "\n";
    }
    fin.close();

    // 生成标准答案
    solve_and_write(n, tree, out_name);
    cout << "Test Case " << id << " [N=" << n << "] finished." << endl;
}

int main() {
    // 测试点分布设计
    make_tree(1, 0, 0);    // 边界：空树
    make_tree(2, 1, 0);    // 边界：单节点
    make_tree(3, 7, 3);    // 示例：小规模满二叉树
    make_tree(4, 100, 1);  // 极端：左斜长链
    make_tree(5, 100, 2);  // 极端：右斜长链
    make_tree(6, 127, 3);  // 结构：较大的满二叉树
    make_tree(7, 500, 0);  // 随机：中等规模
    make_tree(8, 800, 0);  // 随机：较大规模
    make_tree(9, 1000, 0); // 随机：上限规模
    make_tree(10, 1000, 0);// 随机：上限规模

    return 0;
}

数据说明及优化分析

1. 测试点覆盖逻辑：

   • Case 1 & 2：处理空输入和单点。NOI 比赛中，很多选手的 BFS 队列如果不判空就会在这里崩溃。
   • Case 4 & 5：极端斜树。测试递归深度是否会触发栈溢出（虽然 $N=1000$ 较小，但对于更大数据量这是必测项）。
   • Case 3, 6, 7-10：各种形状的二叉树，测试翻转后层序遍历的正确性。

2. 性能与安全性：

   • 非递归生成：答案生成函数 solve_and_write 使用了 BFS（队列），完全避开了递归调用，哪怕你以后将 $N$ 放大到 $10^6$，该生成器也不会爆栈。
   • 无除法运算：代码中仅涉及整数加减和随机数索引，彻底杜绝了“除以零”异常。
   • 时间复杂度：生成一棵树及对应答案的时间复杂度为 $O(N)$。生成全部 10 组数据的时间在 100ms 左右，极速且稳定。

3. 文件大小控制：

   • 即使是 $N=1000$ 的数据点，.in 文件大小约为 $20 \sim 30KB$，.out 文件约为 $5 \sim 10KB$。
   • 全套 10 组数据的总压缩包大小将控制在 200KB 左右，远低于你要求的 2MB，非常适合 OJ 传输和存储。

4. 选手建议：

   • 告诉你的学生，在读入数据时，如果 $N=0$ 必须立刻 return 0，否则后续对数组下标 0 的访问（如 tree[0]）虽然在某些环境下不报错，但在严格的 NOI 评测机上可能导致意外。

你可以直接编译并运行这个 gen.cpp，它会在当前目录下为你准备好全部的测试数据。祝辅导顺利！

作为教练，我将带你从最经典的递归写法开始，逐步进阶到竞赛级别的迭代与静态内存优化写法。

在翻转二叉树时，核心逻辑非常简单：“把当前节点的左右孩子互换，然后递归地去翻转这两棵子树”。

版本一：基础递归 DFS（最直观的 NOI 满分思路）

思路分析： 二叉树的问题天然具有自相似性。翻转一棵树，等于翻转其左右子树，再把左右子树的位置交换。

• 时间复杂度：$O(N)$，每个节点恰好访问一次。
• 空间复杂度：$O(H)$，取决于树的高度。最坏情况（链状树）为 $O(N)$，平均情况为 $O(\log N)$。

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

using namespace std;

// NOI风格：通常使用静态数组模拟树结构
const int MAXN = 1005;
struct Node {
    int val;
    int l, r;
} tree[MAXN];

// 递归翻转函数
void invertDFS(int u) {
    if (u == -1) return; // 递归边界：空节点返回

    // 【关键点】交换当前节点的左右子节点索引
    swap(tree[u].l, tree[u].r);

    // 【递归点】继续翻转交换后的左右子树
    invertDFS(tree[u].l);
    invertDFS(tree[u].r);
}

// 层序遍历输出函数
void printLevelOrder(int n) {
    if (n == 0) return;
    queue<int> q;
    q.push(0); // 根节点入队
    bool first = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (!first) cout << " ";
        cout << tree[u].val;
        first = false;
        if (tree[u].l != -1) q.push(tree[u].l);
        if (tree[u].r != -1) q.push(tree[u].r);
    }
    cout << endl;
}

int main() {
    int n;
    if (!(cin >> n) || n == 0) return 0;

    for (int i = 0; i < n; ++i) {
        cin >> tree[i].val >> tree[i].l >> tree[i].r;
    }

    invertDFS(0);      // 1. 执行翻转
    printLevelOrder(n); // 2. 输出翻转后的层序遍历

    return 0;
}

版本二：标准 BFS 迭代版（稳健，防止爆栈）

思路分析： 在处理深度可能达到 $10^5$ 的二叉树时，递归会面临系统栈溢出的风险。使用队列（BFS）不仅能翻转树，还能直接控制遍历顺序。

• 时间复杂度：$O(N)$。
• 空间复杂度：$O(W)$，其中 $W$ 是树的最大宽度。

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 1005;
struct Node {
    int val, l, r;
} tree[MAXN];

void invertBFS(int n) {
    if (n == 0) return;
    queue<int> q;
    q.push(0);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 【关键点】在出队时进行交换操作
        swap(tree[u].l, tree[u].r);

        // 将交换后的孩子（如果不为空）加入队列继续处理
        if (tree[u].l != -1) q.push(tree[u].l);
        if (tree[u].r != -1) q.push(tree[u].r);
    }
}

int main() {
    ios::sync_with_stdio(false); // NOI 常用输入优化
    cin.tie(0);

    int n;
    if (!(cin >> n) || n == 0) return 0;

    for (int i = 0; i < n; ++i) {
        cin >> tree[i].val >> tree[i].l >> tree[i].r;
    }

    invertBFS(n);

    // 复用 BFS 逻辑输出结果（翻转后的层序遍历）
    queue<int> q;
    q.push(0);
    bool first = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (!first) cout << " ";
        cout << tree[u].val;
        first = false;
        if (tree[u].l != -1) q.push(tree[u].l);
        if (tree[u].r != -1) q.push(tree[u].r);
    }
    cout << endl;

    return 0;
}

版本三：最优性能版（手动队列与数组优化）

思路分析： 在 NOI 考场上，追求极致的运行速度和最小的内存碎片是高手的习惯。

• 优化点：使用 scanf/printf 替代 cin/cout，使用数组模拟队列。
• 空间分配：将左右子节点分开存储在两个数组 L[MAXN] 和 R[MAXN] 中，进一步提高 CPU 缓存命中率。

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1005;
int Val[MAXN], L[MAXN], R[MAXN];
int que[MAXN]; // 手动模拟队列

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0) return 0;

    for (int i = 0; i < n; ++i) {
        scanf("%d %d %d", &Val[i], &L[i], &R[i]);
    }

    // 1. 翻转逻辑：可以用简单的循环遍历所有节点进行交换（因为题目保证给定的是所有节点）
    // 或者用 BFS 确保只翻转可达节点
    int head = 0, tail = 0;
    que[tail++] = 0;
    while (head < tail) {
        int u = que[head++];
        // 原地交换左右索引
        swap(L[u], R[u]);
        if (L[u] != -1) que[tail++] = L[u];
        if (R[u] != -1) que[tail++] = R[u];
    }

    // 2. 输出逻辑：利用刚才 BFS 已经生成的 que 数组（就是翻转后的层序序列）
    for (int i = 0; i < tail; ++i) {
        printf("%d%c", Val[que[i]], (i == tail - 1 ? '\n' : ' '));
    }

    return 0;
}

复杂度分析思考过程

1. 时间复杂度 ($O(N)$):

   • 思考：无论哪种方法，我们都需要“触达”树中的每一个节点并执行一次 swap。
   • 计算：节点数 $N$，边数 $N-1$。遍历过程耗时与 $N$ 成线性关系。

2. 空间复杂度 ($O(N)$):

   • 递归法：消耗的是系统栈（Stack）。在树退化为链时，深度为 $N$。
   • 迭代法：消耗的是堆内存中的队列。在完全二叉树时，队列最宽处约为 $N/2$。
   • 结论：在 $N=10^4$ 以上规模，应优先考虑迭代法以规避系统栈限制。

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

   • 原地修改：不要尝试创建新树或拷贝节点，直接在读入的数组上修改索引。
   • 静态化：在 NOI 竞赛中，尽量避免使用 new 或 std::list，静态数组模拟是性能最优解。

总结：读题关键词与坑点

• “翻转” (Invert)：核心动作是 swap(left, right)。
• “层序遍历” (Level Order)：输出要求的关键词。这意味着你即使在 DFS 翻转后，最后也需要用 BFS 来输出结果。
• $n=0$ 情况：边界条件。在竞赛中，空输入经常作为测试点，必须有 if (n == 0) 的判断。
• 节点编号 vs 节点值：注意输入中给的是编号（用于索引数组），而输出要求的是节点对应的值 Val[i]。这是新手最容易混淆的地方。

希望这个进阶过程能帮你打好树论的基础！加油！