作为教练，我为你准备了一个高效的二叉树数据生成器。它能够生成 10 个测试点，涵盖了 空树、单节点、完全二叉树、极端链状树（卡 DFS 逻辑陷阱） 等各种情况。

为了确保生成器自身的稳定性，生成答案的代码采用了迭代 BFS 算法，有效防止在处理 $10^5$ 规模的链状树时发生爆栈。

C++ 数据生成器代码

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

using namespace std;

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

// ---------------------------------------------------------
// 核心：使用迭代 BFS 计算最小深度 (用于生成 .out 文件)
// 确保即使在 N=10^5 的链状树下也不会爆栈
// ---------------------------------------------------------
int solve_min_depth(int n, const vector<Node>& tree) {
    if (n <= 0) return 0;
    
    queue<pair<int, int>> q; // <节点编号, 当前深度>
    q.push({0, 1});
    
    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();
        
        int u = curr.first;
        int d = curr.second;
        
        // 判定叶子节点：这是寻找最小深度的终点
        if (tree[u].l == -1 && tree[u].r == -1) {
            return d;
        }
        
        if (tree[u].l != -1) q.push({tree[u].l, d + 1});
        if (tree[u].r != -1) q.push({tree[u].r, d + 1});
    }
    return 0;
}

// ---------------------------------------------------------
// 树构造函数
// ---------------------------------------------------------
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(-1000, 1000);

    // 预填随机值
    for (int i = 0; i < n; ++i) tree[i].val = val_dist(rng);

    if (type == 1) { // 极端右链 (LeetCode 示例 2 模型)
        for (int i = 0; i < n - 1; ++i) tree[i].r = i + 1;
    } 
    else if (type == 2) { // 极端左链
        for (int i = 0; i < n - 1; ++i) tree[i].l = i + 1;
    }
    else if (type == 3) { // 完全二叉树 (最小深度应为 logN)
        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 if (type == 4) { // "深浅不一"树：一边极深，一边极浅
        tree[0].l = 1; // 极深侧
        for (int i = 1; i < n - 2; ++i) tree[i].l = i + 1;
        tree[0].r = n - 1; // 极浅侧叶子节点
    }
    else { // 随机二叉树
        vector<int> has_space; 
        has_space.push_back(0);
        for (int i = 1; i < n; ++i) {
            // 随机选一个有空位的父节点
            int idx = uniform_int_distribution<int>(0, (int)has_space.size() - 1)(rng);
            int p = has_space[idx];
            
            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;
                has_space.erase(has_space.begin() + idx); // 满了，移除
            } else {
                tree[p].r = i;
                has_space.erase(has_space.begin() + idx); // 满了，移除
            }
            has_space.push_back(i); // 新节点有空位
        }
    }

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

    // 写入 .out
    fout << solve_min_depth(n, tree) << endl;

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

int main() {
    // 1-2: 边界测试
    make_test_case(1, 0, 0);   // 空树
    make_test_case(2, 1, 0);   // 单节点
    
    // 3: 满二叉树
    make_test_case(3, 1023, 3); 

    // 4-5: 极端链状 (测试 N=10^5 情况下的逻辑和稳定性)
    make_test_case(4, 100000, 1); // 全部右偏，最小深度应为 100000
    make_test_case(5, 100000, 2); // 全部左偏

    // 6: 结构性陷阱测试
    make_test_case(6, 50000, 4);  // 根节点右边就是叶子，左边是长链

    // 7-10: 不同规模随机树
    make_test_case(7, 5000, 0);
    make_test_case(8, 20000, 0);
    make_test_case(9, 50000, 0);
    make_test_case(10, 80000, 0); // 保持总文件大小在合理范围

    return 0;
}

数据说明与辅导建议

1. 复杂度分析与文件大小

• 时间复杂度：构树采用随机选择父节点并维护空位列表的方法，复杂度约为 $O(N)$。生成 10 个测试点（包括两个 $10^5$ 的大文件）在常规 PC 上约需 1-2 秒。
• 空间复杂度：$O(N)$，用于存储树结构。
• 文件大小：$N=10^5$ 的 .in 文件约为 1.8MB。为了保证 10 个文件的总大小平衡，随机案例（7-10）设定在 $5 \times 10^4$ 左右，确保全套数据在 10MB 以内，单点满足区分度。

2. 测试点设计的针对性

• 测试点 4 & 5：这是“坑点”。如果学生的代码简单地写 min(left, right) + 1，由于链状树的一侧深度总是 0，他们的输出会错误地变成 1。
• 测试点 6：专门测试 BFS 的优势。BFS 会立刻在根节点的右侧发现叶子节点并退出，而 DFS 可能会先深入左侧的 50000 层长链。

3. 异常处理

• 除以零：生成器在随机选择父节点时通过 has_space 动态列表确保分母不为零。
• 爆栈：生成器生成的答案使用 std::queue 迭代实现，不占用系统递归栈。

你可以直接编译并运行该生成器，它会自动产生符合 NOI 规范的测试数据，助你完成 OJ 的搭建！加油！

作为教练，我将为你展示从 递归分治 到 广度优先搜索（BFS） 的进阶过程。这道题的精髓在于对“叶子节点”定义的精准把握，以及在寻找“最小”目标时对搜索策略的选择。

版本一：递归分治法 (DFS)

思路分析： 这是最符合直觉的写法，将大问题拆解为子树的深度问题。

• 易错陷阱：如果直接写 min(get_min(L), get_min(R)) + 1，当遇到只有单侧子树的节点时（如只有右子树），会错误地取左子树的深度 0，导致结果始终为 1。
• 关键逻辑：必须判断子树是否为空。只有当左右子树都存在时，才进行 min 比较。
• 时间复杂度：$O(N)$，需遍历整棵树。
• 空间复杂度：$O(H)$，取决于树的高度。

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

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

int get_min_depth(int u) {
    // 1. 基础边界：空节点深度为0
    if (u == -1) return 0;

    // 2. 核心逻辑：判断是否为叶子节点（左右都为空）
    if (tree[u].l == -1 && tree[u].r == -1) return 1;

    // 3. 递归处理：
    // 如果左子树为空，必须去右子树找叶子
    if (tree[u].l == -1) return get_min_depth(tree[u].r) + 1;
    // 如果右子树为空，必须去左子树找叶子
    if (tree[u].r == -1) return get_min_depth(tree[u].l) + 1;

    // 4. 左右都不为空，取最小值
    return min(get_min_depth(tree[u].l), get_min_depth(tree[u].r)) + 1;
}

int main() {
    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) {
        cin >> tree[i].val >> tree[i].l >> tree[i].r;
    }

    cout << get_min_depth(0) << endl;
    return 0;
}

版本二：标准广度优先搜索 (BFS) —— 最优搜索策略

思路分析： 在寻找“最短路径”或“最小深度”时，BFS 具有天然的优势。

• 早期停止 (Early Exit)：一旦在某一层发现了第一个叶子节点，那么该层即为最小深度。我们不需要遍历叶子节点以下的任何节点。
• 性能优势：在极端不平衡的树（如只有右侧很深的树，但左侧很浅就有叶子）中，BFS 的运行效率远高于 DFS。
• 时间复杂度：$O(N)$，最坏情况遍历全树，平均优于 DFS。
• 空间复杂度：$O(W)$，$W$ 为树的最大宽度。

#include <iostream>
#include <queue>

using namespace std;

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

struct State {
    int id, depth;
};

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

    queue<State> q;
    q.push({0, 1}); // 根节点编号为0，初始深度为1

    while (!q.empty()) {
        State cur = q.front();
        q.pop();

        int u = cur.id;
        int d = cur.depth;

        // 【关键点】找到第一个叶子节点立刻返回答案
        if (tree[u].l == -1 && tree[u].r == -1) {
            return d;
        }

        // 非叶子节点，继续向下探索
        if (tree[u].l != -1) q.push({tree[u].l, d + 1});
        if (tree[u].r != -1) q.push({tree[u].r, d + 1});
    }
    return 0;
}

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

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

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

版本三：NOI 极限优化版 (手动队列 + 链式结构思维)

思路分析： 针对 $10^5$ 级别的数据，如果树退化成链，DFS 会面临爆栈风险。此版本使用数组模拟队列，并配合快速 I/O，是 NOI 考场上冲击满分的写法。

• 优化点：避免 std::queue 的容器开销，使用固定大小的静态数组。
• 时间优化：使用 scanf 提高读入效率。

#include <cstdio>

const int MAXN = 100005;

struct Node {
    int l, r;
} tree[MAXN];

// 手动模拟队列
int q_id[MAXN];
int q_dep[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, &tree[i].l, &tree[i].r);
    }

    int head = 0, tail = 0;
    // 根节点入队
    q_id[tail] = 0;
    q_dep[tail] = 1;
    tail++;

    while (head < tail) {
        int u = q_id[head];
        int d = q_dep[head];
        head++;

        // 判定叶子节点：此为最短路径终点
        if (tree[u].l == -1 && tree[u].r == -1) {
            printf("%d\n", d);
            return 0;
        }

        // 入队子节点
        if (tree[u].l != -1) {
            q_id[tail] = tree[u].l;
            q_dep[tail] = d + 1;
            tail++;
        }
        if (tree[u].r != -1) {
            q_id[tail] = tree[u].r;
            q_dep[tail] = d + 1;
            tail++;
        }
    }

    return 0;
}

复杂度分析思考过程

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

   • 无论是 DFS 还是 BFS，每个节点最多被处理一次。
   • BFS 的优势：在二叉树高度极大的随机情况下，BFS 往往只需要扫描很少比例的节点就能找到叶子，而 DFS 必须完整探索完第一条路径。

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

   • DFS: 空间取决于递归深度。在最坏的“链状”情况下，空间复杂度为 $O(N)$。在 NOI 评测环境中，如果系统栈（Stack Limit）设为 8MB，处理 $10^5$ 深度极易 RE。
   • BFS: 空间取决于队列。最大宽度出现在完全二叉树的底层，空间复杂度为 $O(N)$。

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

   • 快速 I/O: 对于 $N \ge 10^5$ 的题目，scanf 或手写 read() 函数可以比 cin 节省大量时间。
   • 内存池/静态数组: 尽量使用全局静态数组存储树结构。动态申请内存（new 或 malloc）在竞赛中速度较慢且容易产生碎片。

读题关键词总结

• “最小深度”：暗示可能存在“提前终止”的搜索策略，首选 BFS。
• “叶子节点”：这是题目最核心的约束条件。必须检查左且右同时为空。
• “1.0s / 256MB”：这告诉我们 $O(N)$ 的算法是绝对安全的，且内存绰绰有余。重点应放在防止爆栈和逻辑正确性上。

加油，理解了 BFS 在最短路问题上的应用，你离 NOI 奖牌又近了一步！