LeetCode算法系列（Java版） 104. 二叉树的最大深度
LeetCode算法系列（Java版） 111. 二叉树的最小深度
力扣原题
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
解题思路
-
实现方式：DFS（深度优先搜索） -
当前节点 root 为空时，说明此处树的高度为 0，0 也是最小值 -
当前节点 root 的左子树和右子树都为空时，说明此处树的高度为 1，1 也是最小值 -
如果为其他情况，则说明当前节点有值，且需要分别计算其左右子树的最小深d度，返回最小深度 +1，+1 表示当前节点存在有 1 个深度
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
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);
}
return ans + 1;
}
}
复杂度分析
-
时间复杂度：，其中 是树的节点数。对每个节点访问一次。
-
空间复杂度：，其中 是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。
LeetCode算法系列（Java版） 104. 二叉树的最大深度
LeetCode算法系列（Java版） 111. 二叉树的最小深度
原文始发于微信公众号（白菜说技术）：LeetCode算法系列 111. 二叉树的最小深度
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/172706.html
