题目
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.
思路
最短路径的定义是从root到叶子节点的最少节点数，从root开始递归查找，对于每个节点需要判断子节点的情况：
- 左子节点为空，右子节点不为空：继续查找右子节点
- 左子节点不为空，右子节点为空：继续查找左子节点
- 左右子节点都不为空：分别查找两个子节点并返回两者较小的值
- 左右子节点都为空：直接返回
上述四种情况可以进一步合并，只要考虑一个子节点为空，另一个子节点不为空的特殊情况：因为空节点返回值为0，所以只要将左右两个子节点的返回值相加就可以了；其他情况只要无脑取两个子节点的较小返回值。
1
\
2
/
3
因为要找到叶子节点，对于节点2，不能直接取两个子节点的较小值。
python代码
# 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):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
if root.left == None or root.right == None:
return self.minDepth(root.left) + self.minDepth(root.right) + 1
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
