☆打卡算法☆LeetCode 111、二叉树的最小深度 算法解析
☆打卡算法☆LeetCode 111、二叉树的最小深度 算法解析
恬静的小魔龙
发布于 2022-08-07 10:26:51
发布于 2022-08-07 10:26:51
一、题目
1、算法题目
“给定一个二叉树，找出其最小深度。”
题目链接：
来源：力扣（LeetCode）
链接： 111. 二叉树的最小深度
2、题目描述
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明： 叶子节点是指没有子节点的节点。
image.png
示例 1：
输入： root = [3,9,20,null,null,15,7]
输出： 2示例 2：
输入： root = [2,null,3,null,4,null,5,null,6]
输出： 5二、解题
1、思路分析
这道题首先想到的就是深度优先搜索的方法，遍历整棵树，找出最小深度。
对于每一个非根节点，只需要分别计算左右子树的最小子节点深度。
也就是把大问题转化为小问题，那么这个问题就可以递归解决。
2、代码实现
代码参考：
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int min_depth = Integer.MAX_VALUE;
if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}
return min_depth + 1;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(N)
其中N是树的节点数，对每个节点只访问一次。
空间复杂度： O(H)
其中H是树的高度，空间复杂度主要取决于递归时的开销，递归的空间复杂度为O(N)，平均情况下树的高度与节点数的对数正相关，空间复杂度为O(log N)，总的时间复杂度就是O(H)。
三、总结
这道题用了广度优先搜索方法，同样，也可以使用广度优先搜索的方法去遍历整棵树。
对于这道题来书，广度优先搜索方法可以保证最先搜索到的叶子节点的深度一定最小。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-04-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录