111. 二叉樹(shù)的最小深度
給定一個(gè)二叉樹(shù)，找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

解法1

DFS算法

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        if root.left is None and root.right is None:
            return 1
        elif not root.left:
            return 1+self.minDepth(root.right)
        elif not root.right:
            return 1+self.minDepth(root.left)
        else:
            return min(self.minDepth(root.right), self.minDepth(root.left)) + 1

解法2

BFS算法

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        if root.left and root.right:
            return min(self.minDepth(root.right), self.minDepth(root.left)) + 1
        else:
            return max(self.minDepth(root.right), self.minDepth(root.left)) + 1

解法3

思路: 逐層遍歷, 用一個(gè)list存儲(chǔ)每一層的左右子節(jié)點(diǎn), 然后得出最早出現(xiàn)的葉子節(jié)點(diǎn)在第幾層.

class Solution:
    def minDepth(self, root):
        if not root:
            return 0
        nodes = [root]
        level = 1
        while len(nodes) > 0:
            sub_nodes = []
            for node in nodes:
                if not node.left and not node.right:
                    return level
                if node.left:
                    sub_nodes.append(node.left)
                if node.right:
                    sub_nodes.append(node.right)
            nodes = sub_nodes
            level += 1