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

yipeiwu_com6年前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-while 计算100以内奇数和的方法

如下所示: sum = 0 n = 99 while n > 0: sum = sum + n n = n - 2 print(sum) 只要条件满足,就不断循环,条...

python进程类subprocess的一些操作方法例子

subprocess.Popen用来创建子进程。 1)Popen启动新的进程与父进程并行执行,默认父进程不等待新进程结束。 复制代码 代码如下: def TestPopen(): &nb...

浅谈解除装饰器作用(python3新增)

一个装饰器已经作用在一个函数上,你想撤销它,直接访问原始的未包装的那个函数。 假设装饰器是通过 @wraps 来实现的,那么你可以通过访问 wrapped 属性来访问原始函数: &g...

对python中Librosa的mfcc步骤详解

1.对语音数据归一化 如16000hz的数据,会将每个点/32768 2.计算窗函数:(*注意librosa中不进行预处理) 3.进行数据扩展填充,他进行的是镜像填充("reflect"...

快速排序的算法思想及Python版快速排序的实现示例

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。 1.分治法的基本思想...