55-Ⅰ二叉树的深度

剑指 Offer 55 - I. 二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，

   3
  / \
 9  20
   /  \
  15   7

返回它的最大深度 3 。

解题思路：

实际上是一个后序遍历，拿到左右子树中的较大深度，然后加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)$。