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