這期內容當中小編將會給大家帶來有關python二叉樹最小深度是什么，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
給定一個二叉樹，找出其最小深度。
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
說明: 葉子節點是指沒有子節點的節點。
示例:
給定二叉樹 [3,9,20,null,null,15,7],
返回它的最小深度 2.
補全下面代碼：
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
分析過程的開始，我們先看一個錯誤的求解，并說明為什么它是錯誤的：
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
if not root.left and not root.right:
return 1
return 1 + min(self.minDepth(root.left),self.minDepth(root.right))
考慮下面二叉樹：
使用以上代碼返回最小深度為 1，其實最小深度為 2，因為最小深度的定義為：從根節點到最近葉子節點的最短路徑上的節點數量。
為什么上面的解有問題呢？
原因在于遞歸基選取有問題，只考慮了下面兩種情況：
遞歸基未考慮下面兩種情況，所以導致出錯：
正確的求解，需要把上面遺漏的兩種遞歸基考慮進去:
# 遞歸基的下面兩種情況必須考慮進去：
if not root.left:
return 1 + self.minDepth(root.right)
if not root.right:
return 1 + self.minDepth(root.left)
正確的完整代碼如下：
class Solution(object):
def minDepth(self, root):
if not root:
return 0
if not root.left and not root.right:
return 1
# 遞歸基的下面兩種情況必須考慮進去：
if not root.left:
return 1 + self.minDepth(root.right)
if not root.right:
return 1 + self.minDepth(root.left)
return 1 + min(self.minDepth(root.left),self.minDepth(root.right))
上述就是小編為大家分享的python二叉樹最小深度是什么了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
