104/111. 二叉树的最大、最小深度

1. 先写出通项公式，就是左右孩子都不为空的情况。
2. 退出条件常为root为空返回0。
3. 思考只有一个结点(没有左右孩子的时候)，左右孩子都是传回0，这个时候带入通项公式是否成立，并获得返回值x。
4. 考虑只有左孩子的时候(左孩子为一个结点)，左孩子传回的应该是x，右孩子传回的是0，带入通项公式，考虑是否成立。

• 最大深度

    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

• 最小深度，注意其中一个孩子不为None，另一个孩子为None的情况

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

• 最小深度bfs解法，判断当前结点是否为叶子结点。

def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        queue = [root]
        level = 1
        while queue:
            n = len(queue)
            for i in range(n):
                cur = queue.pop(0)
                if not cur.left and not cur.right:
                    return level
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            level += 1