111. 二叉樹的最小深度

難度簡單689

給定一個二叉樹，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。

圖一

第一次錯誤解法：

這種解法無法解決如下圖中的情況

image.png

這種情況下，返回的答案是1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        else:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

第二次錯誤

修改以上錯誤，把節(jié)點(diǎn)為空時的返回值變大（私以為比1大即可，但是后續(xù)發(fā)現(xiàn)是錯誤的），

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 100
        if not root.left and not root.right:
            return 1
        else:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

我的最終解法：

提交之后，發(fā)現(xiàn)有個結(jié)構(gòu)如圖一，但是有1800多個節(jié)點(diǎn)的用例，沒有通過，返回值是101，這時候我才意識到，節(jié)點(diǎn)空時的返回值不是比1大即可，隨著遞歸的進(jìn)行，必須要比最深層那個空節(jié)點(diǎn)返回值大才行，那么就無窮大啦！
另外，第一次根節(jié)點(diǎn)為空的情況沒法判斷了，改成子函數(shù)形式。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        def minDepthFun(root):
            if not root:
                return float('inf')   # 設(shè)置為無窮大
            if not root.left and not root.right:
                return 1
            else:
                return 1 + min(minDepthFun(root.left), minDepthFun(root.right))
        if not root:
            return 0
        else:
            return minDepthFun(root)

官方解法

官方解法的關(guān)鍵在于，將左右節(jié)點(diǎn)為空的情況分別討論，分別遞歸

深度優(yōu)先遍歷

對于每一個非葉子節(jié)點(diǎn)，我們只需要分別計(jì)算其左右子樹的最小葉子節(jié)點(diǎn)深度。這樣就將一個大問題轉(zhuǎn)化為了小問題，可以遞歸地解決該問題。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        if not root.left and not root.right:
            return 1
        
        min_depth = 10**9
        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth)
        
        return min_depth + 1

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

廣度優(yōu)先遍歷

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        que = collections.deque([(root, 1)])
        while que:
            node, depth = que.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                que.append((node.left, depth + 1))
            if node.right:
                que.append((node.right, depth + 1))
        
        return 0

作者：LeetCode-Solution
鏈接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。