给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]
   3
  /  \
9   20
  /   \
  15  7
返回它的最大深度 3 。

解法 1

DFS，利用深度优先搜索，遍历二叉树的每条路径，若当前节点不为空，则判断左子树和右子树的深度，返回其中最大的子树深度并加上 1（当前节点）。若当前节点为空则返回 0。由所有叶子节点回溯到根节点时，即可计算出二叉树最大深度。

def max_depth(root):
    if not root:
        return 0
    return max(max_depth(root.left), max_depth(root.right)) + 1

执行用时 :48 ms
内存消耗 :14.6 MB

时间复杂度：O(n)
空间复杂度：在最糟糕的情况下，树是完全不平衡的，例如每个结点只剩下左子结点，递归将会被调用 n 次（树的高度），因此保持调用栈的存储将是 O(n)。但在最好的情况下（树是完全平衡的），树的高度将是 log(n)。因此，在这种情况下的空间复杂度将是 O(log(n))。

解法 2

BFS，利用广度优先搜索，遍历二叉树的每一层，如果当前节点是叶子节点，那么当前层级数即为该叶子节点深度。如果当前叶子节点深度大于最大深度，则更新最大深度。

def max_depth(root):
    stack = []
    depth = 0
    if root is not None:
        stack.append((1, root))
    while stack:
        current_depth, root = stack.pop()
        if root is not None:
            depth = max(depth, current_depth)
            stack.append((current_depth + 1, root.left))
            stack.append((current_depth + 1, root.right))
    return depth

执行用时 :40 ms
内存消耗 :14.2 MB

时间复杂度：O(n)
空间复杂度：O(n)

如果是求最小深度呢？

解法 1

DFS，和求最大深度一样，遍历二叉树的每条路径。需要注意的是，当某个子树为空时，还需要计算另一个非空子树的深度，两个子树都为空的节点才是叶子节点。

def min_depth(root):
    if not root:
        return 0
    if not root.left:
        return min_depth(root.right) + 1
    if not root.right:
        return min_depth(root.left) + 1
    return min(min_depth(root.left), min_depth(root.right)) + 1

执行用时 :44 ms
内存消耗 :14.8 MB

时间复杂度：O(n)
空间复杂度：O(n)

解法 2

BSF，和最大深度一样，遍历二叉树的每一层，需要注意的是，这里利用队列先进先出的特性来存储节点，并进行层次遍历，第一个子节点的层级深度即为最小深度。

def min_depth(root):
    if not root:
        return 0
    else:
        node_deque = deque([(1, root), ])

    while node_deque:
        depth, root = node_deque.popleft()
        children = [root.left, root.right]
        if not any(children):
            return depth
        for c in children:
            if c:
                node_deque.append((depth + 1, c))

执行用时 :44 ms
内存消耗 :14.3 MB

时间复杂度：O(n)
空间复杂度：O(n)，最坏的情况要遍历到最后一层

参考

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/