104. Maximum Depth of Binary Tree

题目：给定一棵二叉树，返回最大深度

方法一：递归，运行40ms

class Solution(object):
    def maxDepth(self, root):
    	if not root: return 0
        return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))
1
2
3
4

方法二：层次遍历，运行28ms

class Solution(object):
    def maxDepth(self, root):
    	depth = 0
        level = [root] if root else []  # 记录每一层的节点
        while level:   
            depth += 1
            level = [kid for n in level for kid in (n.left,n.right) if kid]
        return depth
1
2
3
4
5
6
7
8

111. Minimum Depth of Binary Tree

题目：给定一棵二叉树，返回最小深度

方法一：Wrong answer

像求最大深度一样写，返回的是左右子树的最小深度，但是这样是错误的
考虑特殊情况：当二叉树是一条链时，最小深度就是链长，而不是为1

class Solution(object):
    def maxDepth(self, root):
    	if not root: return 0
        return 1 + min(self.maxDepth(root.left),self.maxDepth(root.right))
1
2
3
4

方法二：改进以上方法

class Solution(object):
    def minDepth(self, root):
        if not root: return 0
        if not root.left: return self.minDepth(root.right) + 1
        if not root.right: return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
1
2
3
4
5
6