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

yipeiwu_com5年前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/

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python Django给admin添加Action的方法实例详解

Python Django给admin添加Action的方法实例详解

在使用Django自带的admin后台的时候,他提供了一些默认的指令可以对数据进行操作, 比如批量删除,修改等   同样的我们也可以添加自己的指令。 创建一个Django项目...

利用Pyhton中的requests包进行网页访问测试的方法

利用Pyhton中的requests包进行网页访问测试的方法

为了测试一组网页是否能够访问,采取python中的requests包进行批量的访问测试,并输出访问结果。 一、requests包的安装 打开命令行(win+r输入cmd启动); 打开p...

Django 多表关联 存储 使用方法详解 ManyToManyField save

当models中使用ManyToManyField进行多表关联的时候,需要使用字段的add()方法来增加关联关系的一条记录,让两个实例关联起来才能顺利保存关联关系 #models.p...

创建pycharm的自定义python模板方法

在pycharm上依次选择打开File->settings->Editor->File andCode Templates->Python Script 复制以下...

python重试装饰器的简单实现方法

简单实现了一个在函数执行出现异常时自动重试的装饰器,支持控制最多重试次数,每次重试间隔,每次重试间隔时间递增。 最新的代码可以访问从github上获取 https://github.co...