Python怎么實(shí)現(xiàn)二叉樹的最小深度

這篇文章將為大家詳細(xì)講解有關(guān)Python怎么實(shí)現(xiàn)二叉樹的最小深度，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

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

最小深度是從根節(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ū)別在于對(duì)“結(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)

關(guān)于“Python怎么實(shí)現(xiàn)二叉樹的最小深度”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。