Python怎么實現二叉樹的最小深度

這篇文章將為大家詳細講解有關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)

關于“Python怎么實現二叉樹的最小深度”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。