104. 二叉树的最大深度

Origin: LeetCode 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

我的解法

function maxDepth(root: TreeNode | null): number {
    const dfs = (node: TreeNode | null): number => {
        if (!node) return 0;
        const leftDepth = dfs(node.left);
        const rightDepth = dfs(node.right);
        return Math.max(leftDepth, rightDepth) + 1;
    };
    return dfs(root);
}

和标准解法逻辑一致，区别是用了一个内部 dfs 闭包。两种写法等价，但闭包写法有扩展优势：以后如果 dfs 需要额外参数（当前路径、父节点引用等），不用改动外部函数签名。

解题思路（草稿）

递归（DFS）——标准解法

最大深度 = 左右子树深度的较大值 + 1。

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

就三行。递归的本质：整棵树的最大深度这个问题，可以拆成”左右子树各自的最大深度”这两个同样形状的子问题。

• 终止条件：空节点深度为 0
• 递推：max(左深度, 右深度) + 1，+1 是当前这一层

和层序遍历的关系

你已经做过 102. 层序遍历（BFS），层序的层数就是最大深度。所以 BFS 也能解：每处理完一层深度 +1，队列空了返回层数。

BFS:  一层一层数，数到最后就是深度      → 适合求"最小"深度（可能提前结束）
DFS:  递归到底，取左右最大值           → 求最大深度更自然

求最大深度 DFS 更简洁；如果是求最小深度（111 题），BFS 反而可能提前剪枝。

复杂度

• 时间：O(n)，每个节点访问一次
• 空间：O(h)，递归栈深度 = 树高，最坏（链状树）O(n)

关联

• 树 - 树的题型总览
• 102. 二叉树的层序遍历 - BFS 视角看同一问题
• 111. 最小深度 - 对偶题，BFS 更合适