111. 二叉树的最小深度

思路

递归时考虑几种情况：
1.左右子树都为空，则最小深度=1（只有根节点）（也可理解为 min(0,0)+1）
2.左子树为空，右子树不空，则最小深度=右子树最小深度+1
3.左子树不为空，右子树为空，最小深度=左子树最小深度+1
4.左右子树不为空，最小深度=左右子树最小深度+1
+1原因：递归的是左右子树,找到最小深度后，还要加上根节点即为整个二叉树的最小深度

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def minDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if root is None:
            return 0
        #左右子树为空
        if root.left is None and root.right is None:
            return 1
        #左子树为空情况
        if root.left is None and root.right is not None:
            return self.minDepth(root.right)+1
        #右子树为空情况
        if root.left is not None and root.right is None:
            return self.minDepth(root.left)+1
        #左右子树不为空情况
        return min(self.minDepth(root.left),self.minDepth(root.right))+1