Python实现二叉树的最小深度的两种方法
作者：求兵 发布时间：2022-05-24 03:30:17
标签：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/
来源：https://blog.csdn.net/qiubingcsdn/article/details/82419605
0
投稿猜你喜欢
- 很多组织机构慢慢的在不同的服务器和地点部署SQL Server数据库——为各种应用和目的&m
- 本文实例讲述了PHP实现二维数组中的查找算法。分享给大家供大家参考，具体如下：方法1：silu从左下角最后一行的第一个元素开始，遍历。如果小
很多人都听过WAMP这个词吧，首先来看WAMP是什么意思？Windows下的Apache+MySQL+PHP，称为WAMP。属于WAMP环境- 软硬件环境OS X EI CapitanPython 3.5.1mysql 5.6前言在开发中经常涉及到数据库的使用，而python对于数据
- 最近稍稍有点空闲时间，于是重新温习了一下之前学习过的python基础。废话不多说，记录一下自己的所得。首先，安装什么的不在本人的温习范围，另
- 假如某个电脑生产商，它的数据库中保存着整机和配件的产品信息。用来保存整机产品信息的表叫做pc；用来保存配件供货信息的表叫做parts。在pc
- 如下所示：import cv2 # [1]导入OpenCv开源库import numpy as npimage_path = "F
- 一.gb2312,gbk,utf8等支持多字节编码的字符集都可以储存汉字，gb2312中的汉字数量远少于gbk，而gb2312,gbk等都可
- 具体代码如下所示：import numpy as npfrom matplotlib import pyplot as pltfrom sc
- Hello，各位读者朋友们好啊，我是小张~这不国庆嘛，就把最近很火的一个韩剧《鱿鱼游戏》刷了下，这部剧整体剧情来说还是非常不错的，很值得一看
- 变量类型ECMAScript变量可能包含两种不同类型的数据值：基本类型和引用类型。基本类型基本类型指的是简单的数据段，5种基本数据类型：un
- 1，FCKeditor 编辑器最新版本: 2.3.1站点：http://www.fckeditor.net 演示：http://w
- 认识模块对于模块，在前面的一些举例中，已经涉及到了，比如曾经有过：import random (获取随机数模块)。为了能够对模块有一个清晰的
- mongodb是基于分布式文件存储的nosql(非关系型)数据库虽说是nosqldb, but mongodb 其中的文档可以是关系型的在m
- 当很多人发现在DW4中定义CSS很方便的时候，开始报怨FP2000不能定义CSS，甚至就此抨击FP2000如何的不好。事实上，在FP2000
- 在这系列视觉设计的文章间隙插一篇字体单位的文章。前文说了，字体单位应该用em而不用px，原因简单来说就是支持IE6下的字体缩放，在页面中按c
- 一、PsutilPython当中的Psutil模块是个跨平台库，它能够轻松获取系统运行的进程和系统利用率，包括CPU、内存、磁盘、网络等信息
- txt文件转换为XML很多目标检测的模型都是默认需要VOC的文件输入格式手上数据label是txt文件。为了避免不必要的bug，还是选择转换
- 数据增强的必要性深度学习在最近十年得以风靡得益于计算机算力的提高以及数据资源获取的难度下降。一个好的深度模型往往需要大量具有label的数据
- 1、某汽车网站地址2、使用firefox查看后发现，此网站的信息未使用json数据，而是简单那的html页面而已3、使用pyquery库中的
