Minimum Depth of Binary Tree

题目描述

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.

解题方法

• Min Depth的recursion和max depth有所不同，因为是要选最小值，所以当前点为None时这并不是一个可以返回0的最小值，如果返回0 的话会被min()函数所取，而是应该在比较时将它省去，因为它不是一个叶子节点，所以返回最大整数，而这又和一开始root为None要 返回0矛盾，所以要用一个helper函数。
• 叶子节点时返回1，否则继续向下面子树寻找叶子节点

Solution

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return self.helper(root)

    def helper(self, root):
        if not root:
            return sys.maxint
        if not root.left and not root.right:
            return 1
        return 1 + min(self.helper(root.left), self.helper(root.right))

Reference