写点什么

手撸二叉树之最小深度

发布于: 7 小时前
手撸二叉树之最小深度

Hello, 大家好,今天是我参加 8 月更文的第 10 天,今天给大家带来的关于二叉树相关的算法题是二叉树的最小深度,正文如下:

题目:

给定一个二叉树,找出其最小深度。


最小深度是从根节点到最近叶子节点的最短路径上的节点数量。


说明:叶子节点是指没有子节点的节点。


示例 1:



输入:root = [3,9,20,null,null,15,7]输出:2
复制代码


示例 2:


输入:root = [2,null,3,null,4,null,5,null,6]输出:5
复制代码

解题思路

首先可以想到使用深度优先搜索的方法,遍历整棵树,记录最小深度。


对于每一个非叶子节点,我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题,可以递归地解决该问题。


  • 当前节点 root 为空时,说明此处树的高度为 0,0 也是最小值。

  • 当前节点 root 的左子树和右子树都为空时,说明此处树的高度为 1,1 也是最小值。

  • 如果为其他情况,则说明当前节点有值,且需要分别计算其左右子树的最小深度,返回最小深度 +1,+1 表示当前节点存在有 1 个深度。

代码实现

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    public int minDepth(TreeNode root) {        if(root == null){            return 0;        } else if (root.left == null) {            return minDepth(root.right) + 1;        } else if (root.right == null){            return minDepth(root.left) + 1;        } else {            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;        }    }}
复制代码

最后

复杂度分析


  • 时间复杂度:O(N),其中 N 是树的节点数。对每个节点访问一次。

  • 空间复杂度:O(H),其中 H 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 O(N)。平均情况下树的高度与节点数的对数正相关,空间复杂度为 O(log N)。

发布于: 7 小时前阅读数: 2
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
手撸二叉树之最小深度