原始题目：剑指 Offer 55 - I. 二叉树的深度 (opens new window)

解题思路：

实际上是一个后序遍历，拿到左右子树中的较大深度，然后加1返回。

递归函数：

• **递归参数：**根节点 $root$。
• 终止条件： $root$ 为 $null$ 时，直接返回。
• 递推工作：
  1. 递归计算左子树的深度 $dl$ ；
  2. 递归计算右子树的深度 $dr$；
  3. 比较 $dl$ 和 $dr$ ，选择较大者然后加一返回。

代码：

public int maxDepth(TreeNode root) {
    if(root == null) {
        return 0;
    }
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

复杂度分析：

• 时间复杂度$O(N)$：$N$ 为树节点的个数，计算深度需要遍历所有的节点。
• 空间复杂度$O(N)$：最长情况下，需要进行 $N$ 次递归，需要栈空间为 $O(N)$。