手撸二叉树之最小深度
Hello, 大家好,今天是我参加 8 月更文的第 10 天,今天给大家带来的关于二叉树相关的算法题是二叉树的最小深度,正文如下:
题目:
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明:叶子节点是指没有子节点的节点。
示例 1:
复制代码
示例 2:
复制代码
解题思路
首先可以想到使用深度优先搜索的方法,遍历整棵树,记录最小深度。
对于每一个非叶子节点,我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题,可以递归地解决该问题。
当前节点 root 为空时,说明此处树的高度为 0,0 也是最小值。
当前节点 root 的左子树和右子树都为空时,说明此处树的高度为 1,1 也是最小值。
如果为其他情况,则说明当前节点有值,且需要分别计算其左右子树的最小深度,返回最小深度 +1,+1 表示当前节点存在有 1 个深度。
代码实现
复制代码
最后
复杂度分析
时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。
空间复杂度:O(H),其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关,空间复杂度为 O(log N)。
版权声明: 本文为 InfoQ 作者【HelloWorld杰少】的原创文章。
原文链接:【http://xie.infoq.cn/article/38111e4c367c046ad3af83435】。文章转载请联系作者。
评论