Python實(shí)現(xiàn)二叉樹的最小深度的兩種方法
找到給定二叉樹的最小深度
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量
注意：葉子節(jié)點(diǎn)沒有子樹
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
1：算法遍歷二叉樹每一層，一旦發(fā)現(xiàn)某層的某個(gè)結(jié)點(diǎn)無子樹，就返回該層的深度，這個(gè)深度就是該二叉樹的最小深度
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：用遞歸解決該題和"二叉樹的最大深度"略有不同。主要區(qū)別在于對“結(jié)點(diǎn)只存在一棵子樹”這種情況的處理，在這種情況下最小深度存在的路徑肯定包括該棵子樹上的結(jié)點(diǎn)
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/
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
- Python對稱的二叉樹多種思路實(shí)現(xiàn)方法
- python3實(shí)現(xiàn)在二叉樹中找出和為某一值的所有路徑(推薦)
- Python3 翻轉(zhuǎn)二叉樹的實(shí)現(xiàn)
- Python3實(shí)現(xiàn)二叉樹的最大深度
- Python3 合并二叉樹的實(shí)現(xiàn)
- 用Python實(shí)現(xiàn)二叉樹、二叉樹非遞歸遍歷及繪制的例子
- 基于python二叉樹的構(gòu)造和打印例子
- Python 二叉樹的層序建立與三種遍歷實(shí)現(xiàn)詳解
- python3實(shí)現(xiàn)二叉樹的遍歷與遞歸算法解析(小結(jié))
- 如何在Python中創(chuàng)建二叉樹
相關(guān)文章
Python進(jìn)程間通信 multiProcessing Queue隊(duì)列實(shí)現(xiàn)詳解
這篇文章主要介紹了python進(jìn)程間通信 mulitiProcessing Queue隊(duì)列實(shí)現(xiàn)詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-09-09
Pytorch學(xué)習(xí)筆記DCGAN極簡入門教程
網(wǎng)上GAN的教程太多了，這邊也談一下自己的理解，本文給大家介紹一下GAN的兩部分組成，有需要的朋友可以借鑒參考下，希望能夠有所幫助2021-09-09
這篇文章主要介紹了輕松掌握Python中的if和循環(huán)判斷技巧的相關(guān)資料,需要的朋友可以參考下2023-11-11
Python實(shí)現(xiàn)圖算法、堆操作和并查集代碼實(shí)例
這篇文章主要介紹了Python實(shí)現(xiàn)圖算法、堆操作和并查集代碼實(shí)例,圖算法、堆操作和并查集是計(jì)算機(jī)科學(xué)中常用的數(shù)據(jù)結(jié)構(gòu)和算法，它們在解決各種實(shí)際問題中具有重要的應(yīng)用價(jià)值,需要的朋友可以參考下2023-08-08
pyenv與virtualenv安裝實(shí)現(xiàn)python多版本多項(xiàng)目管理
這篇文章主要介紹了pyenv與virtualenv安裝實(shí)現(xiàn)python多版本多項(xiàng)目管理過程，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-08-08
Python使用mmap實(shí)現(xiàn)內(nèi)存映射文件操作
內(nèi)存映射通?？梢蕴岣逫/O的性能，本文主要介紹了Python使用mmap實(shí)現(xiàn)內(nèi)存映射文件操作，分享給大家，感興趣的可以了解一下2021-06-06
這篇文章主要為大家介紹了5種Python單例模式的實(shí)現(xiàn)方式，所謂單例，是指一個(gè)類的實(shí)例從始至終只能被創(chuàng)建一次，對單例感興趣的小伙伴們可以參考一下2016-01-01
這篇文章主要介紹了Python小程序之在圖片上加入數(shù)字的代碼，這個(gè)是小編今天練手的小程序，代碼簡單易懂，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-11-11
這篇文章主要介紹了numpy多維數(shù)組索引的問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-05-05
這篇文章主要介紹了OpenCV中VideoCapture類的使用詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02