你好！我是你的 OI 金牌教练。今天我们来研究二叉树属性计算中的另一个经典问题——二叉树的最小深度。

这道题虽然看似与“最大深度”对称，但其中隐藏着一个非常经典的思维陷阱，在 NOI 系列竞赛（如 CSP-J/S）中，这类考察基本定义理解的题目经常作为“防 AK”或区分细节把控能力的题目出现。

一、 题目描述 (NOI 规范版)

题目名称：二叉树的最小深度 (min_depth_binary_tree) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 注意： 叶子节点是指没有子节点的节点。如果一个节点只有一个子节点，它并不是叶子节点。

【输入格式】 输入文件包含多行，描述二叉树的结构： 第一行一个整数 $n$，表示节点总数。 接下来的 $n$ 行，每行描述一个节点的信息：首先是该节点的值 $v$，然后是该节点的左子节点编号 $L$，最后是右子节点编号 $R$。 （注：节点编号从 0 到 $n-1$，根节点固定为 0。如果子节点不存在，则编号为 -1。如果 $n=0$，则表示空树。）

【输出格式】 输出一个整数，表示二叉树的最小深度。

【样例 1 输入】

5
3 1 2
9 -1 -1
20 3 4
15 -1 -1
7 -1 -1

【样例 1 输出】

2

(说明：路径 3 -> 9 的节点数为 2)

【样例 2 输入】

5
2 -1 1
3 -1 2
4 -1 3
5 -1 4
6 -1 -1

【样例 2 输出】

5

【数据范围】

• 节点总数 $0 \le n \le 10^5$
• 节点值在 $[-1000, 1000]$ 之间

二、 预备知识点

1. 叶子节点定义：必须满足 left == -1 && right == -1。
2. DFS (分治思想)：如何正确处理“单传”子树的情况。
3. BFS (广度优先搜索)：利用层序遍历，第一个被发现的叶子节点所在的层数即为最小深度（这是寻找最短路径的最优策略）。
4. 边界处理：$n=0$ 时的特殊返回。

三、 启发式思维导图：教练的草稿纸

请跟我一起在草稿纸上分析这个逻辑陷阱：

1. 逻辑陷阱分析

假设有一棵树：根节点 A 只有右孩子 B，没有左孩子。

• 错误逻辑：min(depth(left), depth(right)) + 1 $\rightarrow$ min(0, 1) + 1 = 1。
• 原因：根节点 A 不是叶子节点，最小深度不能在这里停止！
• 正确逻辑：必须走到叶子节点。如果左子树为空，最小深度取决于右子树；反之亦然。

2. BFS 的天然优势

• 想象你从根节点开始放水。
• 水一层一层往下流。
• 谁先变成干涸的（遇到叶子节点），谁就是答案。
• 在寻找“最短/最小”时，BFS 通常比 DFS 更高效，因为它不需要遍历整棵树。

3. 复杂度预估

• 时间复杂度：$O(N)$。每个节点最多入队出队一次。
• 空间复杂度：$O(N)$。取决于队列大小或递归深度。

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

在 NOI 竞赛中，为了避开繁琐的分类讨论，推荐使用 BFS。

方案 A：递归 DFS (注意分类讨论)

graph TD
    Start(开始 DFS node) --> CheckNull{node 为空?}
    CheckNull -- 是 --> Ret0(返回 0)
    CheckNull -- 否 --> CheckLeaf{是叶子节点?}
    CheckLeaf -- 是 --> Ret1(返回 1)
    CheckLeaf -- 否 --> LeftNull{左孩子为空?}
    LeftNull -- 是 --> RecurRight(递归右子树并加 1)
    LeftNull -- 否 --> RightNull{右孩子为空?}
    RightNull -- 是 --> RecurLeft(递归左子树并加 1)
    RightNull -- 否 --> Compare(取左右递归最小值再加 1)

方案 B：迭代 BFS (寻找最短路径的标准做法)

graph TD
    Start(开始 BFS) --> CheckEmpty{n 等于 0?}
    CheckEmpty -- 是 --> Ret0(返回 0)
    CheckEmpty -- 否 --> Init(初始化队列 Q 并存入根节点和深度 1)
    Init --> WhileQ{Q 不为空?}
    WhileQ -- 是 --> Pop(弹出队首节点 u 和其深度 d)
    Pop --> IsLeaf{u 是叶子节点?}
    IsLeaf -- 是 --> Final(返回当前深度 d)
    IsLeaf -- 否 --> PushChild(将 u 的非空子节点入队并带上深度 d+1)
    PushChild --> WhileQ
    WhileQ -- 否 --> End(结束)

五、 关键读题技巧

1. 关键词：叶子节点 (Leaf Node)：
   • 这是整道题的灵魂。读题时如果忽略了“到叶子节点”的路径，代码在处理单侧树时必错。
2. 关键词：最小 (Minimum)：
   • 在搜索树中，看到“最小/最短”应优先考虑 BFS。
3. 数据范围 $10^5$：
   • 注意 $10^5$ 量级下，递归深度如果过大（退化成链）可能会爆系统栈（Stack Overflow）。
   • 优化建议：在 NOI 比赛中，若树高可能很大，建议手动调大栈空间或改用 BFS。

六、 教练总结

• 最大深度：比较随性，max(l, r) + 1 即可。
• 最小深度：比较挑剔，只有当两侧都有孩子时才用 min；若有一侧为空，必须走不为空的那一侧。

现在，请根据这些思路，尝试用 C++14 实现它。记得特别处理 $n=0$ 的情况！加油！