LeetCode 集锦(二十七) - 第 111 题 Minimum Depth Of Binary Tree

栏目: 数据库 · 发布时间: 5年前

内容简介:本题相对而言也是简单的,求一颗树的最小高度,所以首先要注意最小高度的定义:最小深度是从根节点到最近叶子节点的最短路径上的节点数。这边需要注意几个点:
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

解题思路

本题相对而言也是简单的,求一颗树的最小高度,所以首先要注意最小高度的定义:最小深度是从根节点到最近叶子节点的最短路径上的节点数。这边需要注意几个点:

  1. 要是叶子节点,叶子节点指的是没有子节点的节点。如果只是一个节点为努力了,那样子不算叶子节点。
  2. 是最近的叶子节点。 其他其实按照最大深度的方式去执行,就可以做到了

解题方法

  1. 按照思路来编写结果

    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》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java语言程序设计

Java语言程序设计

(美) Y. Daniel Liang / 李娜 / 机械工业出版社 / 2011-6 / 75.00元

本书是Java语言的经典教材,多年来畅销不衰。本书全面整合了Java 6的特性,采用“基础优先,问题驱动”的教学方式,循序渐进地介绍了程序设计基础、解决问题的方法、面向对象程序设计、图形用户界面设计、异常处理、I/O和递归等内容。此外,本书还全面且深入地覆盖了一些高级主题,包括算法和数据结构、多线程、网络、国际化、高级GUI等内容。 本书中文版由《Java语言程序设计:基础篇》和《Java语......一起来看看 《Java语言程序设计》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

MD5 加密
MD5 加密

MD5 加密工具

html转js在线工具
html转js在线工具

html转js在线工具