111. 二叉树的最小深度

难度简单689

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

图一

第一次错误解法：

这种解法无法解决如下图中的情况

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))

第二次错误

修改以上错误，把节点为空时的返回值变大（私以为比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 100
        if not root.left and not root.right:
            return 1
        else:
            return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

我的最终解法：

提交之后，发现有个结构如图一，但是有1800多个节点的用例，没有通过，返回值是101，这时候我才意识到，节点空时的返回值不是比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:
        def minDepthFun(root):
            if not root:
                return float('inf')   # 设置为无穷大
            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)

官方解法

官方解法的关键在于，将左右节点为空的情况分别讨论，分别递归

深度优先遍历

对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

广度优先遍历

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。