内容简介:本题相对而言也是简单的,求一颗树的最小高度,所以首先要注意最小高度的定义:最小深度是从根节点到最近叶子节点的最短路径上的节点数。这边需要注意几个点:
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its minimum depth = 2. 复制代码
翻译:
给定一个二叉树,求它的最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数。
注意:叶子是没有子节点的节点。
例子:
给定如下树[3,9,20,null,null,15,7]:
3 / \ 9 20 / \ 15 7 复制代码
返回 最小深度:2
解题思路
本题相对而言也是简单的,求一颗树的最小高度,所以首先要注意最小高度的定义:最小深度是从根节点到最近叶子节点的最短路径上的节点数。这边需要注意几个点:
- 要是叶子节点,叶子节点指的是没有子节点的节点。如果只是一个节点为努力了,那样子不算叶子节点。
- 是最近的叶子节点。 其他其实按照最大深度的方式去执行,就可以做到了
解题方法
-
按照思路来编写结果
public int minDepth(TreeNode root) { if (root == null) { return 0; } int right = minDepth(root.right) + 1; int left = minDepth(root.left) + 1; int min = Math.min(left, right); //判断是否有空的节点 if (min <= 1) { return Math.max(right, left); } return min; } public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } 复制代码
时间复杂度: 该方案用了遍历的方式,所以为O(n)=O(n)
空间复杂度: 该方案没有使用额外的空间,所以空间复杂度O(n)=O(1)
以上所述就是小编给大家介绍的《LeetCode 集锦(二十七) - 第 111 题 Minimum Depth Of Binary Tree》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Google是如何控制世界的
(美)丹尼尔·伊克比亚 / 李军 / 东方出版社 / 2008-08 / 36.00元
秘Google的发展之路! Google,这个有着数百亿的网页存储量、每天两亿搜索次数的搜索引擎,最初仅仅是一个方程式。这个由拉里·佩奇和塞吉·布林两位天才创造出的超级算法甚至比可口可乐的配方还要保密。 当广告公司为自己网页在搜索结果中的排序争得头破血流时,Google正悠然地坐收渔翁之利,这种天才的拍卖广告链接的商业模式给Google带来了令人瞠目结舌的企业利润!仅仅从1999~20......一起来看看 《Google是如何控制世界的》 这本书的介绍吧!