111 minimum depth of binary tree

111. Minimum Depth of Binary Tree

题目: https://leetcode.com/problems/minimum-depth-of-binary-tree/

难度:

Easy

思路，看完题目我想当然的认为就是直接递归取最小的值，代码如下：

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return 1 + min(map(self.minDepth, (root.left, root.right)))

但是没过，有一种特殊情况就是

注意leaf node反正就是没有left和right的

比如下图

1
 \
  2

2是一个孩子节点

这种情况应该输出2而不是1

唯一的特殊情况就是上面这种了，因为root下只有一个左节点或者是右节点，这样另外一边的空节点并不算是leaf node

leaf node: itself is not null but it has both children null

因此要避免这种情况，代码改成下面：

# Definition for a binary tree node.
# 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 not root:
            return 0
        depth_under_root = map(self.minDepth, (root.left, root.right))
        return 1 + (min(depth_under_root) or max(depth_under_root))

所以还是要养成多写edge case的好习惯，也许就帮你避免了general写法的特例,代码如下

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

---

我们一直在努力

apachecn/AiLearning

---