给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [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/
