104.二叉树的最大深度

二叉树的最大深度

给定一个二叉树 root，返回其 最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

• 树中节点的数量在 [0, $10^4$] 区间内
• -100 <= Node.val <= 100

解析

递归求解，树的最大深度等于左右子树最大深度的较大值加 1。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

最简洁的递归写法，时间复杂度 O(n)。