Python实现二叉树的最小深度的两种方法

找到给定二叉树的最小深度

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

注意：叶子节点没有子树

Example:

Given binary tree [3,9,20,null,null,15,7],

3
   / \
  9  20
    /  \
   15   7
return its minimum depth = 2.

1：算法遍历二叉树每一层，一旦发现某层的某个结点无子树，就返回该层的深度，这个深度就是该二叉树的最小深度

def minDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
      return 0
    curLevelNodeList = [root]
    minLen = 1
    while curLevelNodeList is not []:
      tempNodeList = []
      for node in curLevelNodeList:
        if not node.left and not node.right:
          return minLen
        if node.left is not None:
          tempNodeList.append(node.left)
        if node.right is not None:
          tempNodeList.append(node.right)
      curLevelNodeList = tempNodeList
      minLen += 1
    return minLen

2：用递归解决该题和"二叉树的最大深度"略有不同。主要区别在于对“结点只存在一棵子树”这种情况的处理，在这种情况下最小深度存在的路径肯定包括该棵子树上的结点

def minDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
      return 0
    if not root.left and root.right is not None:
      return self.minDepth(root.right)+1
    if root.left is not None and not root.right:
      return self.minDepth(root.left)+1
    left = self.minDepth(root.left)+1
    right = self.minDepth(root.right)+1
    return min(left,right)

算法题来自：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python3实现二叉树的最大深度

    问题提出: 给定一个二叉树,找出其最大深度.二叉树的深度为根节点到最远叶子节点的最长路径上的节点数. 说明: 叶子节点是指没有子节点的节点. 解决思路:递归法求解.从根结点向下遍历,每遍历到子节点depth+1. 代码实现(￣▽￣): # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Non

  • Python实现二叉树的最小深度的两种方法

    找到给定二叉树的最小深度 最小深度是从根节点到最近叶子节点的最短路径上的节点数量 注意:叶子节点没有子树 Example: Given binary tree [3,9,20,null,null,15,7], 3    / \   9  20     /  \    15   7 return its minimum depth = 2. 1:算法遍历二叉树每一层,一旦发现某层的某个结点无子树,就返回该层的深度,这个深度就是该二叉树的最小深度 def minDepth(self, root):

  • 使用Python实现租车计费系统的两种方法

    要求: #出租车计费************************************************************************************** # 要求:循环输入公里数,自动计算所需费用,费用计算公式如下 # 0.公里数小于等于0时输出: #   请输入正确的公里数进行计算,程序结束 # 1.出租车起步价8元,包含2公里 # 2.超过两公里的部分,每公里收取1.2元 # 3.超过12公里的部分,每公里收取1.5元 方法一: while True:

  • python实现嵌套列表平铺的两种方法

    方法一:使用列表推导式 >>> vec = [[1,2,3],[4,5,6],[7,8,9]] >>> get = [num for elem in vec for num in elem] >>> get [1, 2, 3, 4, 5, 6, 7, 8, 9] 方法相当于 >>> vec = [[1,2,3],[4,5,6],[7,8,9]] >>> result = [] >>> for ele

  • Python实现AES加密，解密的两种方法

    第一种 import base64 from Crypto.Cipher import AES # 密钥(key), 密斯偏移量(iv) CBC模式加密 def AES_Encrypt(key, data): vi = '0102030405060708' pad = lambda s: s + (16 - len(s) % 16) * chr(16 - len(s) % 16) data = pad(data) # 字符串补位 cipher = AES.new(key.encode('utf8

  • Python爬虫后获取重定向url的两种方法

    下面给大家分享Python爬虫后获取重定向url的两种方法,具体内容如下所示: 方法(一) # 获得重定向url from urllib import request # https://zhidao.baidu.com/question/681501874175782812.html url = "https://www.baidu.com/link?url=IscBx0u8h9q4Uq3ihTs_PqnoNWe7slVWAd2dowQKrnqJedvthb3zrh9JqcMJu3ZqFrbW

  • python向json中追加数据的两种方法总结

    目录 前言 1. list dump (不推荐) 2. json update (推荐使用) 总结 前言 json以其轻量级的数据交换格式,且易于阅读和编写而使用率很广泛,而使用json的过程中时而需要增加字段,本人验证两种方式之后将其集成梳理. 具体操作详情如下: 1. list dump (不推荐) 采用list方式,向json中添加字段.此法存在一定的问题,不推荐使用. 方法如下: (1)先创建一个列表: json_content = [] (2)将当前json文件中已有的内容读入列表中:

  • Python创建相同值数组/列表的两种方法

    目录 题目要求 解决方法 方法一:使用Python基础语法 方法二:使用numpy包的函数实现 参考资料 总结 题目要求 现在有这样的一个需求:创建一个数组或列表,列表中的所有值是相同的. 解决方法 找到两种解决方法,第一种是使用Python的基础语法,第二种是借助numpy包提供的函数实现.分别为大家进行介绍. 方法一:使用Python基础语法 使用“*”号可以实现列表的创建,使用非常简单,以下示例将会创建长度为20的列表. 另外,不仅可以复制单个元素,还可以实现多个元素的复制,如下示例: 方

  • python读取视频流提取视频帧的两种方法

    本文实例为大家分享了python读取视频流提取视频帧的具体代码,供大家参考,具体内容如下 方法一:通过imageio库和skimage库 1. 安装环境: pip install imageio pip install skimage 这时候会报错Please install the `scikit-image` package (instead of `skimage`) 所以按照提示操作即可: pip install scikit-image 环境安装成功. 2.通过python安装ffmp

  • 使用Python获取字典键对应值的两种方法

    使用Python获取字典键对应值的两种方法

    目录 当知道字典的键时: 当不知道字典的键时: 附:字典dic最大值对应的键 总结 有两种方法 当知道字典的键时: unit_rooms={ 3:{301:[1,80],302:[1,80],303:[2,90],304:[2,90]}, 4:{401:[1,80],402:[1,80],403:[2,90],404:[2,90]}, 5:{501:[1,80],502:[1,80],503:[2,90],504:[2,90]} } for i in range(3,6): rooms=unit

  • 判断python字典中key是否存在的两种方法

    今天来说一下如何判断字典中是否存在某个key,一般有两种通用做法,下面为大家来分别讲解一下: 第一种方法:使用自带函数实现. 在python的字典的属性方法里面有一个has_key()方法,这个方法使用起来非常简单. 例: #生成一个字典 d = {'name':{},'age':{},'sex':{}} #打印返回值 print d.has_key('name') #结果返回True 第二种方法:使用in方法 #生成一个字典 d = {'name':{},'age':{},'sex':{}}

随机推荐