0111. Minimum Depth of Binary Tree
==================================
题目信息
--------
:题号: 0111. 二叉树的最小深度
:难度: Easy
:主题: 二叉树、根到叶路径、广度优先搜索、提前结束
:原题: `LeetCode 0111 `_
:重点: 区分空孩子与叶节点,修正递归最小值状态,再利用 BFS 的深度顺序在首个叶节点停止
题目重述
--------
给定二叉树根节点 ``root``,返回从根到最近叶节点的路径所包含的节点数。叶节点必须同时没有左孩子和右孩子;
只有一个孩子的节点不是叶节点,缺失的孩子位置也不能当作一条已结束路径。空树的最小深度为 ``0``。
树中节点总数在 ``0..10^5`` 范围内,节点值在 ``-1000..1000`` 范围内。节点值不影响答案,算法不修改树。
自建示例
--------
* 多个最近叶:``root = [6,2,9,null,4,8,12,null,null,7]``,返回 ``3``,节点 ``4``、``12`` 都是
深度 ``3`` 的叶节点;
* 单侧链:``root = [5,null,7,null,9]``,返回 ``3``,缺失的左孩子不能使 ``5`` 或 ``7`` 提前结束;
* 单节点:``root = [3]``,返回 ``1``;
* 空树:``root = []``,返回 ``0``。
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
private:
int recursiveMinimumDepth(TreeNode* node) {
if (!node) {
return 0;
}
if (!node->left) {
return 1 + recursiveMinimumDepth(node->right);
}
if (!node->right) {
return 1 + recursiveMinimumDepth(node->left);
}
return 1 + std::min(recursiveMinimumDepth(node->left), recursiveMinimumDepth(node->right));
}
int breadthFirstMinimumDepth(TreeNode* root) {
if (!root) {
return 0;
}
std::queue pending;
pending.push(root);
int depth = 1;
while (!pending.empty()) {
const int levelSize = static_cast(pending.size());
for (int count = 0; count < levelSize; ++count) {
TreeNode* node = pending.front();
pending.pop();
if (!node->left && !node->right) {
return depth;
}
if (node->left) {
pending.push(node->left);
}
if (node->right) {
pending.push(node->right);
}
}
++depth;
}
return 0;
}
public:
int minDepth(TreeNode* root) {
return breadthFirstMinimumDepth(root);
}
};
题解
----
原始路径搜索
~~~~~~~~~~~~
最小深度来自某条根到叶路径。最直接的正确思路是枚举所有根到叶路径:沿孩子继续搜索,只在节点同时没有
左右孩子时记录当前路径长度,最后取所有叶深度的最小值。检查全部叶节点显然覆盖所有合法终点。
关键在“合法终点”。空指针只表示某个孩子不存在,并不是树中的叶节点。若当前节点只有右孩子,根到叶路径
仍必须进入右侧;不能沿缺失的左侧走一步便宣告路径结束。
递归最小值陷阱
~~~~~~~~~~~~~~
最大深度可以统一写成 ``1 + max(leftDepth, rightDepth)``,因为空孩子深度 ``0`` 不会抢走非空侧的较大值。
最小深度若机械改成 ``1 + min(...)`` 就会出错:对 ``[5,null,7,null,9]``,根的左侧返回 ``0``,公式
立即得到 ``1``,却没有到达任何叶节点。
``recursiveMinimumDepth`` 因此区分三类非空节点:
* 左孩子为空时,只能沿右孩子继续;若两侧都空,右递归返回 ``0``,当前叶节点自然得到 ``1``;
* 右孩子为空时,只能沿左孩子继续;
* 两个孩子都存在时,两侧都有合法叶路径,才能取较小深度。
这版递归不需要保存完整路径,只让每棵子树返回到最近叶节点的距离,已经把路径数组压缩为一个整数。它仍可能
为了比较两侧而访问整棵树;而最小值问题还提供了更强的信息:只要按深度递增访问,第一个叶节点就是答案。
按层提前结束
~~~~~~~~~~~~~~
``breadthFirstMinimumDepth`` 使用队列按层处理节点。每轮开始时,队列中的 ``levelSize`` 个节点处于同一深度;
只弹出这批节点,处理中加入的孩子留到下一轮。完成整层后才递增 ``depth``。
当弹出一个同时没有左右孩子的节点时,可以立即返回当前深度。此时所有更浅节点已经检查完且都不是叶节点,
队列中剩余节点与当前节点同深或更深,尚未入队的节点只会更深,所以不可能再出现更小答案。
对第一个示例,状态为:
.. list-table::
:header-rows: 1
* - 深度
- 本层队列
- 检查结果
- 下一层队列
* - 1
- ``[6]``
- 根不是叶节点
- ``[2,9]``
* - 2
- ``[2,9]``
- 两者都至少有一个孩子
- ``[4,8,12]``
* - 3
- ``[4,8,12]``
- ``4`` 是叶节点,立即返回 3
- 不再生成
``4`` 后面即使还有同层节点,也不需要继续比较;它们最多提供相同深度,不可能改善最小值。
分支顺序与主解
~~~~~~~~~~~~~~
BFS 必须先判断当前节点是否为叶,再把非空孩子入队。若把“一侧为空”误当叶条件,单侧链会提前返回;若不
固定层大小便持续弹出不断增长的队列,``depth`` 将失去层边界。
公开入口采用 BFS。它直接利用“最浅叶”的目标顺序,并避免最多 ``10^5`` 个节点形成单侧链时的深递归栈;
递归方法仍保留,因为它清楚展示了空孩子为何不能参与普通最小值比较。
复杂度分析
~~~~~~~~~~
两种方法最坏都访问全部 ``n`` 个节点,时间为 ``O(n)``。递归工作空间为树高 ``O(h)``;BFS 队列为最大
层宽 ``O(w)``。BFS 遇到最近叶节点时提前结束,实际访问量可能明显小于 ``n``。返回值只占常数空间。