[LeetCode] Minimum Depth of Bina

题目

原题地址

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