温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何解析python二叉树的最小深度

发布时间:2021-12-13 15:25:34 来源:亿速云 阅读:96 作者:柒染 栏目:大数据

如何解析python二叉树的最小深度,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

题目描述

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

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

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

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3
  / \
 9  20
   /  \
  15   7
 

返回它的最小深度  2.

 

解题方案

 

思路

  • 标签:DFS

  • 终止条件、返回值和递归过程:

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

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

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

  • 时间复杂度:O(n),n为树的节点数量

 

代码

  • Java版本

/**
* 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;
   }
}
 
  • JavaScript版本

/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
   if(root == null) {
       return 0;
   }
   if(root.left == null && root.right == null) {
       return 1;
   }
   let ans = Number.MAX_SAFE_INTEGER;
   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;
};
   

画解

如何解析python二叉树的最小深度

如何解析python二叉树的最小深度

如何解析python二叉树的最小深度

如何解析python二叉树的最小深度

看完上述内容,你们掌握如何解析python二叉树的最小深度的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI