作为教练，我为你准备了一个针对 “二叉树最大深度” 题目的全自动化数据生成器。

该生成器采用 C++14 标准，能够生成 10 组涵盖从“空树”到“极端链状树”的测试用例。为了保证在 OJ 评测中能区分算法（特别是递归深度限制），我特意加入了 $N=10^4$ 的极端退化树。

数据生成器设计逻辑

1. 分级测试点：
   • 1-2 (基础边界)：空树 ($N=0$) 和 单节点 ($N=1$)。
   • 3-4 (典型结构)：小规模随机树与完全二叉树（高度 $\log N$）。
   • 5-7 (极端退化)：左斜链、右斜链、之字形链。这些是为了测试选手的程序是否会因为递归过深导致栈溢出（RE）。
   • 8-10 (大规模随机)：$N=10^4$ 的随机二叉树。
2. 安全性：生成器内置的 solve_depth 采用 迭代 BFS 算法，确保在生成 .out 答案时绝对不会爆栈。
3. 合规性：输出格式严格遵循：首行 $N$，随后 $N$ 行 val L R，空位用 -1 表示。

C++ 代码实现

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

using namespace std;

// 节点结构
struct Node {
    int val;
    int left, right;
};

// ---------------------------------------------------------
// 核心：使用迭代 BFS 计算深度，防止生成器自身爆栈
// ---------------------------------------------------------
int solve_depth(int n, const vector<Node>& tree) {
    if (n <= 0) return 0;
    
    queue<pair<int, int>> q; // <节点编号, 深度>
    q.push({0, 1});
    int max_d = 0;
    
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        
        int u = curr.first;
        int d = curr.second;
        max_d = max(max_d, d);
        
        if (tree[u].left != -1) q.push({tree[u].left, d + 1});
        if (tree[u].right != -1) q.push({tree[u].right, d + 1});
    }
    return max_d;
}

// ---------------------------------------------------------
// 树构造函数
// ---------------------------------------------------------
void make_test_case(int id, int n, int type) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);

    if (n == 0) {
        fin << 0 << endl;
        fout << 0 << endl;
        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].left = i + 1;
    } 
    else if (type == 2) { // 极端链状：右斜
        for (int i = 0; i < n - 1; ++i) tree[i].right = i + 1;
    }
    else if (type == 3) { // 极端链状：之字形
        for (int i = 0; i < n - 1; ++i) {
            if (i % 2 == 0) tree[i].left = i + 1;
            else tree[i].right = i + 1;
        }
    }
    else if (type == 4) { // 完全二叉树/满二叉树结构
        for (int i = 0; i < n; ++i) {
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            if (l < n) tree[i].left = l;
            if (r < n) tree[i].right = r;
        }
    }
    else { // 随机二叉树
        // 保证连通：每个节点 i (i>0) 的父节点 p < i
        for (int i = 1; i < n; ++i) {
            int p = uniform_int_distribution<int>(0, i - 1)(rng);
            // 尝试挂载，如果满位了就往后顺延寻找空位
            while (tree[p].left != -1 && tree[p].right != -1) {
                p = (p + 1) % i;
            }
            if (tree[p].left == -1 && tree[p].right == -1) {
                if (rng() % 2) tree[p].left = i; else tree[p].right = i;
            } else if (tree[p].left == -1) {
                tree[p].left = i;
            } else {
                tree[p].right = i;
            }
        }
    }

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

    // 写入输出文件
    fout << solve_depth(n, tree) << endl;

    fin.close();
    fout.close();
    printf("Test Case %d [N=%d, Type=%d] Generated.\n", id, n, type);
}

int main() {
    // 1-2 边界
    make_test_case(1, 0, 0); 
    make_test_case(2, 1, 0);
    
    // 3-4 小规模与满二叉树
    make_test_case(3, 10, 0);
    make_test_case(4, 1023, 4); // 深度为 10 的满二叉树

    // 5-7 极端链状 (测试递归深度，N=10000)
    make_test_case(5, 10000, 1); // 左斜
    make_test_case(6, 10000, 2); // 右斜
    make_test_case(7, 10000, 3); // 之字

    // 8-10 大规模随机
    make_test_case(8, 5000, 0);
    make_test_case(9, 10000, 0);
    make_test_case(10, 10000, 0);

    return 0;
}

给教练（OJ管理员）的提示：

1. 文件大小优化：
   • 该生成器产生的 .in 文件对于 $N=10^4$ 的规模，大小约为 $150KB$。
   • 10 个测试点总大小约 $1.5MB \sim 2MB$，非常适合在校园网或小型 OJ 上传输。
2. 区分度分析：
   • 测试点 5、6、7 是本题的“灵魂”。如果选手使用递归 DFS 且没有在 Linux 评测环境下设置 ulimit -s unlimited（或者 OJ 没有调整系统栈限制），这些点会导致 Runtime Error。
   • 这可以引导学生思考：如何用迭代（BFS 或 模拟栈）去改写递归，这是从 OI 入门级跨越到进阶级的标志。
3. 时间复杂度说明：
   • 生成逻辑中使用了简单的顺延寻找父节点策略，保证了构树是 $O(N)$ 级别的，生成全部 10 组数据通常在 1 秒内完成。
4. 无异常保障：
   • 代码中没有除法运算，避免了 Floating Point Exception。
   • 对 $N=0$ 进行了显式特判，避免了访问 tree[0] 的越界错误。

你可以直接运行此程序，它会在你的当前工作目录下生成 1.in 到 10.out。祝你的竞赛辅导顺利！

作为教练，我将带你从最基础的分治递归开始，逐步过渡到迭代 BFS，最后讨论针对大规模数据的性能优化写法。这道题虽然简单，但它是理解“树形结构递归收缩”逻辑的敲门砖。

版本一：分治递归 DFS（NOI 考场推荐写法）

思路分析： 这是一棵树，它的深度等于“它最高的子树深度 + 1”。

• 递归出口：如果当前节点是空（编号为 -1），则深度为 0。
• 递推逻辑：max_depth(u) = max(max_depth(left), max_depth(right)) + 1。
• 时间复杂度：$O(N)$，每个节点遍历一次。
• 空间复杂度：$O(H)$，系统栈空间取决于树的高度。

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 10005;

// 定义树节点结构
struct Node {
    int val;
    int left, right;
} tree[MAXN];

// 递归函数
int get_depth(int u) {
    // 【关键点】递归终止条件：如果节点为空 (-1)，返回深度 0
    if (u == -1) {
        return 0;
    }
    
    // 【易错点】分治思想：先求左子树深度，再求右子树深度
    int left_h = get_depth(tree[u].left);
    int right_h = get_depth(tree[u].right);
    
    // 返回较大值 + 1（1代表当前节点这一层）
    return max(left_h, right_h) + 1;
}

int main() {
    // 基础优化：解除 cin 同步，提高读入速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n) || n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 读入节点信息
    for (int i = 0; i < n; ++i) {
        // 在本题中，假设读入顺序即为编号 i
        cin >> tree[i].val >> tree[i].left >> tree[i].right;
    }

    // 根节点固定为 0
    cout << get_depth(0) << endl;

    return 0;
}

版本二：广度优先迭代版（稳健的层序遍历）

思路分析： 在某些题目中，树的深度可能非常大（退化成链），递归可能导致系统栈溢出（RE）。使用 std::queue 进行层序遍历可以有效规避这个问题。

• 核心逻辑：每处理完一层，计数器 depth 增加 1。
• 时间复杂度：$O(N)$。
• 空间复杂度：$O(W)$，$W$ 是树的最大宽度。

#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 10005;
struct Node {
    int left, right;
} tree[MAXN];

int bfs_depth(int n) {
    if (n == 0) return 0;

    queue<int> q;
    q.push(0); // 根节点入队
    int depth = 0;

    while (!q.empty()) {
        int sz = q.size(); // 【关键】记录当前层有多少个节点
        depth++; // 只要这层有东西，深度就加 1

        // 处理当前层的所有节点
        for (int i = 0; i < sz; ++i) {
            int u = q.front();
            q.pop();

            // 将下一层的孩子放入队列
            if (tree[u].left != -1) q.push(tree[u].left);
            if (tree[u].right != -1) q.push(tree[u].right);
        }
    }
    return depth;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    for (int i = 0; i < n; ++i) {
        int v;
        cin >> v >> tree[i].left >> tree[i].right;
    }

    cout << bfs_depth(n) << endl;
    return 0;
}

版本三：最优性能版（手动队列与 Fast I/O）

思路分析： 在 NOI 竞赛中，如果 $N \ge 10^6$ 且时限很紧，我们会使用 scanf 或手写 read() 函数，并使用数组模拟队列。

• 优化点：避免 std::queue 的动态内存分配，使用静态数组模拟。

#include <cstdio>
#include <algorithm>

using namespace std;

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

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

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

    int head = 0, tail = 0;
    que[tail++] = 0; // 根节点
    int depth = 0;

    while (head < tail) {
        int sz = tail - head; // 当前层的节点数
        depth++;
        for (int i = 0; i < sz; ++i) {
            int u = que[head++];
            // 压入子节点到队列尾部
            if (L[u] != -1) que[tail++] = L[u];
            if (R[u] != -1) que[tail++] = R[u];
        }
    }

    printf("%d\n", depth);
    return 0;
}

复杂度分析思考过程

1. 时间复杂度分析：

   • DFS 版本：每个节点作为递归函数的参数进入一次，离开一次。$T(N) = O(N)$。
   • BFS 版本：每个节点入队一次，出队一次。$T(N) = O(N)$。
   • 结论：对于树的遍历问题，$O(N)$ 是理论下限。

2. 空间复杂度分析：

   • 递归空间：取决于递归深度。对于平衡二叉树，$H = \log N$；对于退化成链的二叉树，$H = N$。因此最坏情况空间复杂度是 $O(N)$。
   • 队列空间：取决于树的最大宽度。完全二叉树最后一层大约有 $N/2$ 个节点，所以也是 $O(N)$。

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

   • 预分配空间：在 NOI 竞赛中，尽量使用全局静态数组而非 std::vector 或动态 new 节点。
   • I/O 瓶颈：当 $N > 5 \times 10^5$ 时，cin 即使关闭同步也可能比 scanf 慢。此时应考虑使用 fread 快读。

总结：读题关键词在哪里？

1. “最大深度”：
   • 看到这个词，联想递归公式：f(u) = max(f(L), f(R)) + 1。
2. “节点总数 $10^4$”：
   • 这个范围非常小。在 NOI 中，这意味着你可以随意使用递归、STL，甚至一些常数略大的算法。但如果范围是 $10^6$，则必须考虑系统栈空间。
3. “-1 表示不存在”：
   • 这是建图的关键。在递归和迭代中，都要先判断这个值。
4. “根节点固定为 0”：
   • 简化了题意，不需要你去寻找入度为 0 的节点作为根。

教练提示：在考场上，首选递归法，因为它代码量最少，逻辑最清晰。只有当你观察到数据范围巨大且可能存在链状结构时，才考虑切换到迭代 BFS。加油！