0104.二叉树的最大深度
难度：🟢 简单
标签：树、深度优先搜索、广度优先搜索、二叉树、递归
题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解题思路
核心思想
本题的核心是求解树的高度。一个二叉树的最大深度可以通过其子树的深度来定义。具体来说，一棵树的最大深度等于其左子树和右子树最大深度中的较大者，再加上 1（根节点本身）。这是一个天然的递归结构。
思路选择
深度优先搜索（DFS），特别是通过递归实现，是解决此问题最直观和简洁的方法。我们可以定义一个函数来计算以任何给定节点为根的树的最大深度。
关键步骤
递归的终止条件 (Base Case)：如果当前节点
root为null，说明这是一棵空树（或者到达了叶子节点的子节点），其深度为 0。这是递归的出口。递归分解：如果当前节点不为空，我们需要知道其左、右子树的最大深度。 a. 递归调用函数本身来计算左子树的最大深度：
maxDepth(root.left)。 b. 递归调用函数本身来计算右子树的最大深度：maxDepth(root.right)。结果合并：当前树的最大深度就是左右子树最大深度中的较大值，再加上 1（代表当前根节点）。即
1 + Math.max(leftDepth, rightDepth)。
代码实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function (root) {
// Base Case: 如果节点为空，深度为0
if (root === null) {
return 0;
}
// 递归计算左、右子树的深度
let leftDepth = maxDepth(root.left);
let rightDepth = maxDepth(root.right);
// 当前树的深度 = 1 (根节点) + 左右子树深度的较大值
return 1 + Math.max(leftDepth, rightDepth);
};
复杂度分析
时间复杂度：O(n) 其中 n 是树的节点总数。我们必须访问树中的每一个节点一次来计算深度。
空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。在最坏情况下（树退化为一条链），空间复杂度为 O(n)；在最好的情况下（一个完全平衡的树），空间复杂度为 O(log n)。
相关题目
总结
本题是二叉树递归算法的入门级经典题目。其解法完美地体现了分治思想：将一个大问题（求整棵树的深度）分解为两个相同类型的子问题（求左右子树的深度），然后合并子问题的解来得到原问题的解。这是理解和掌握树的递归遍历的基础。