[LeetCode]111. 二叉树的最小深度

111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。

解法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

思路: 逐层遍历, 用一个list存储每一层的左右子节点, 然后得出最早出现的叶子节点在第几层.

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