Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

思路

利用深度优先遍历（DFS），采用递归的方法解决这道问题。

在进行递归的时候，将每次递归的结果存储在数组中，根据题意，返回数组的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    res = []
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if (root):
            self.res = []
            self.DFS(root, 1)
            return min(self.res)
        else:
            return 0
        
    def DFS(self, root, depth):
        if (root):
            if (root.left is None and root.right is None):
                self.res.append(depth)
            else:
                self.DFS(root.left, depth+1)
                self.DFS(root.right, depth+1)