快捷導(dǎo)航

Python實(shí)現(xiàn)二叉樹的最小深度的兩種方法

更新時(shí)間：2019年09月30日 15:04:33 作者：求兵

這篇文章主要介紹了Python實(shí)現(xiàn)二叉樹的最小深度的兩種方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

找到給定二叉樹的最小深度

最小深度是從根節(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í)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

解決pyecharts在jupyter notebook中使用報(bào)錯問題
這篇文章主要介紹了解決pyecharts在jupyter notebook中使用報(bào)錯問題，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-06-06
Python內(nèi)存優(yōu)化的七種技巧分享
本文將重點(diǎn)介紹 Python 的內(nèi)置機(jī)制,并介紹 7 種原始但有效的內(nèi)存優(yōu)化技巧,掌握這些技巧將大大提高你的 Python 編程能力,文中通過代碼示例給大家講解的非常詳細(xì),感興趣的小伙伴跟著小編一起來學(xué)習(xí)吧
2024-02-02
python實(shí)現(xiàn)二分類的卡方分箱示例
今天小編就為大家分享一篇python實(shí)現(xiàn)二分類的卡方分箱示例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-11-11
淺談一下python中threading模塊
這篇文章主要介紹了一下python中threading模塊,threading提供了一個(gè)比thread模塊更高層的API來提供線程的并發(fā)性。這些線程并發(fā)運(yùn)行并共享內(nèi)存,需要的朋友可以參考下
2023-04-04
django 框架實(shí)現(xiàn)的用戶注冊、登錄、退出功能示例
這篇文章主要介紹了django 框架實(shí)現(xiàn)的用戶注冊、登錄、退出功能,結(jié)合實(shí)例形式詳細(xì)分析了Django框架用戶注冊、登陸、退出等功能具體實(shí)現(xiàn)方法及操作注意事項(xiàng),需要的朋友可以參考下
2019-11-11
python 自動去除空行的實(shí)例
今天小編就為大家分享一篇python 自動去除空行的實(shí)例，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧
2018-07-07
python程序封裝為win32服務(wù)的方法
這篇文章主要為大家詳細(xì)介紹了python程序封裝為win32服務(wù)的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-11-11
python 參數(shù)列表中的self 顯式不等于冗余
Self in the Argument List: Redundant is not Explicit
2008-12-12
Python設(shè)計(jì)模式中的備忘錄模式
這篇文章主要為大家詳細(xì)介紹了Python設(shè)計(jì)模式中的備忘錄模式，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2022-02-02
通過python-pptx模塊操作ppt文件的方法
這篇文章主要介紹了通過python-pptx模塊操作ppt文件的方法,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，本文給大家介紹的需要的朋友可以參考下
2020-12-12