Q111 Minimum Depth of Binary Tre

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.

解题思路：

先明白最小路径的定义：从根结点到最近叶子结点的所包含的结点个数（包括根）。

举个例子：

Example1:

      0

 return 1

Example2:

      0
     / 
   -3   
     \
      5

 return 3

Example3:

      0
     / \
   -3   9
       /
      5

return 2

观察几个例子，发现对于例子2，我们只需要找到最大深度即可；对于例子3，我们只需要找到最小深度即可。而例子2和3的区别就在于根节点的左右子树是否全为非空。如果全为非空，找到最小深度；否则，找到最大深度。

Python实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        if root.left != None and root.right != None: 
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1