二叉树的最小深度
# 📃 题目描述
题目链接:111. 二叉树的最小深度 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
# 🔔 解题思路
# 递归法
和求最大深度一样,不过有一点需要注意,举个例子:
3
\
20
/ \
15 7
\
11
这颗二叉树的最小深度是 3,而不是 1。因为题目中指明了,最小深度是从根节点到最近叶子节点的最短路径上的节点数量,一定要走到叶子节点才行。
如果我们还用求最大深度的那段代码:
// 左子树的高度
int leftDepth = maxDepth(root.left);
// 右子树的高度
int rightDepth = maxDepth(root.right);
return Math.min(leftDepth, rightDepth) + 1;
如果这样写的话,没有左孩子的分支显然就会被算作最短深度。
可能有同学会问,求最大深度里也写明了一定要走到叶子节点才行,为什么这段代码就行呢?
太显然了,求最大深度一定会走到叶子节点呀,题目写不写都是一样的,因为如果某个节点他有叶子节点,那求最大深度的时候一定会走到那,对吧;
但是如果求最小深度的话,走到叶子节点反而会增加深度,所以为了防止我们不走到叶子节点,题目才特此写明。
所以,对于求最小深度中的左右子树,我们需要作额外的处理:
- 如果左子树为空,右子树不为空,说明最小深度是 1 + 右子树的深度
- 反之,右子树为空,左子树不为空,最小深度是 1 + 左子树的深度
- 最后如果左右子树都不为空,返回左右子树深度最小值 + 1
具体代码如下:
class Solution {
public int minDepth(TreeNode root) {
// 递归出口
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
// 左子树的高度
int leftDepth = minDepth(root.left);
// 右子树的高度
int rightDepth = minDepth(root.right);
// 左子树为空,右子树不为空
if (leftDepth == 0) {
return rightDepth + 1;
}
// 右子树为空,左子树不为空
else if (rightDepth == 0) {
return leftDepth + 1;
}
// 左右子树都不为空
return Math.min(leftDepth, rightDepth) + 1;
}
}
# 迭代法
同样的,需要注意的是,只有当左右孩子都为空的时候,才说明遍历的最低点了。如果其中一个孩子为空则不是最低点
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
// 根节点入队
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
depth ++;
for (int i = 0; i < size; i ++) {
TreeNode cur = queue.poll();
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
// 只有当左右孩子都为空的时候,才说明遍历的最低点了
if (cur.left == null && cur.right == null) {
return depth;
}
}
}
return depth;
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10