题目

难度：★★☆☆☆
类型：二叉树

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

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

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

示例

示例1:

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度 2.

示例2:

给定二叉树 [1, 2],

    1
   / 
  2  

返回它的最小深度 2.

解答

这道题和【题目104. 二叉树的最大深度】属于同一类别，我们可以采用类似的解法，通过递归来实现。不过不同的是，这里需要考虑一个特殊条件，即当一棵二叉树只有一个左子树或右子树时，我们只能根据这棵已有的子树来确定当前数的最小深度。

1. 当输入根节点为空时，返回None；

2. 调用函数本身获得当前结点的左右子树的最小深度；

3. 当两棵子树的最小深度均不为零时，返回它们的最小值+1；

4. 如果两棵子树中有一棵树的最小深度为零，即该子树为空，则当前数的最小深度取决于另一棵子树的最小深度+1。

class Solution:
    def minDepth(self, root):

        def min_depth(root):                                    # 获得以root为根结点的树的最小深度
            if not root:
                return 0
            left_min_depth = min_depth(root.left)               # 递归获得左子树的最小深度
            right_min_depth = min_depth(root.right)             # 递归获得右子树的最小深度
            if left_min_depth > 0 and right_min_depth > 0:      # 如果左右子树最小深度都不是0
                res = min(left_min_depth, right_min_depth) + 1  # 当前子树的最小深度是两者较小值+1
            else:                                               # 如果有一个子树是空
                res = max(left_min_depth, right_min_depth) + 1      # 当前数的最小深度取决于非空子树，其深度+1
            return res

        return min_depth(root)

（PS：这里我们在函数里又写了一个子函数，是为了便于展示和迁移到其他任务中，不用每次都写self，如果不喜欢这种形式，可以换种写法）