0111. Minimum Depth of Binary Tree¶
题目信息¶
- 题号:
二叉树的最小深度
- 难度:
Easy
- 主题:
二叉树、根到叶路径、广度优先搜索、提前结束
- 原题:
- 重点:
区分空孩子与叶节点,修正递归最小值状态,再利用 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++ 实现¶
#include <algorithm>
#include <queue>
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<TreeNode*> pending;
pending.push(root);
int depth = 1;
while (!pending.empty()) {
const int levelSize = static_cast<int>(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。
当弹出一个同时没有左右孩子的节点时,可以立即返回当前深度。此时所有更浅节点已经检查完且都不是叶节点, 队列中剩余节点与当前节点同深或更深,尚未入队的节点只会更深,所以不可能再出现更小答案。
对第一个示例,状态为:
深度 |
本层队列 |
检查结果 |
下一层队列 |
|---|---|---|---|
1 |
|
根不是叶节点 |
|
2 |
|
两者都至少有一个孩子 |
|
3 |
|
|
不再生成 |
4 后面即使还有同层节点,也不需要继续比较;它们最多提供相同深度,不可能改善最小值。
分支顺序与主解¶
BFS 必须先判断当前节点是否为叶,再把非空孩子入队。若把“一侧为空”误当叶条件,单侧链会提前返回;若不
固定层大小便持续弹出不断增长的队列,depth 将失去层边界。
公开入口采用 BFS。它直接利用“最浅叶”的目标顺序,并避免最多 10^5 个节点形成单侧链时的深递归栈;
递归方法仍保留,因为它清楚展示了空孩子为何不能参与普通最小值比较。
复杂度分析¶
两种方法最坏都访问全部 n 个节点,时间为 O(n)。递归工作空间为树高 O(h);BFS 队列为最大
层宽 O(w)。BFS 遇到最近叶节点时提前结束,实际访问量可能明显小于 n。返回值只占常数空间。