111. 二叉树的最小深度

解法一：递归

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

解法二：BFS

这个方法时间排名非常后，不知道为什么！

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        queue = [root] if root else []
        levels = 0
        while queue:
            levels += 1
            for _ in range(len(queue)):
                node = queue.pop(0)
                if not node.left and not node.right:
                    return levels
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return levels