👨🎓作者:bug菌 ✏️博客:CSDN、掘金等 💌公众号:猿圈奇妙屋 🚫特别声明:原创不易,转载请附上原文出处链接和本文声明,谢谢配合。 🙏版权声明:文章里可能部分文字或者图片来源于互联网或者百度百科,如有侵权请联系bug菌处理。
题目:
给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
具体请看如下示例:
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
提示:
[0, 105]
内-1000 <= Node.val <= 1000
题目来源: LeetCode官网题目难度:⭐⭐
题目给定:最小深度是从根节点到最近叶子节点的最短路径上的节点数量。解题思路还是递归,万金油解题思路!凡是遇到二叉树题,递归也是我最能想到的,哈哈哈,但是还是存在很大的优化空间的,比如深度优先搜索或者广度优先搜索。具体思路及解题步骤请看如下:
AC代码
具体算法代码实现如下:
class Solution {
public int minDepth(TreeNode root) {
//当前节点为空,直接返回0
if(root == null) {
return 0;
}
//左右节点皆空,直接返回1.
if(root.left == null && root.right == null) {
return 1;
}
//若当前节点有值,则分别计算左右节点的最小深度。
int ans = Integer.MAX_VALUE;
//计算左节点的最小深度。
if(root.left != null) {
ans = Math.min(minDepth(root.left), ans);
}
//计算右节点的最小深度。
if(root.right != null) {
ans = Math.min(minDepth(root.right), ans);
}
//进行+1
return ans + 1;
}
}
leetcode提交运行结果截图如下:
复杂度分析:
如上就是采用的深度优先搜索思路进行的破题,还有我提到的广度优先,不知道大家对这种思路解法是否了解,你们也可以去试试,这里我就不给大家都演示了,我是觉得写起来代码上是有些不同的,你们去试试就知道啦。
再者,解题道路千万条,欢迎小伙伴们脑洞大开,如果你们有啥更好的想法或者思路,欢迎评论区告诉我哦,大家一起互相借鉴互相学习,方能成长的更快。
好啦,以上就是本期的所有内容啦,咱们下期见咯。