LC104 二叉树的最大深度 · 逐题动画 · RuntimeScope

当前：LC104 · 二叉树的最大深度 · 首次出现于 Day 16 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

LC104 · 二叉树的最大深度 · 工程执行实验室

每个节点向父节点汇报自己的高度

最大深度 = 根到最远叶子路径上的节点数（不是边数）。后序 DFS：子树先汇报，父节点再汇总 1 + max(left, right)。

最长路径：3 → 20 → 15

节点数 = 3 · 空树 = 0 · 单节点 = 1

核心 · 后序高度汇报

最大深度 = 从根节点到最远叶子节点路径上的节点数（数节点，不数边）。

· 最大深度 = 根到最远叶子路径上的节点数，不是边数。
· 空树深度为 0，单节点树深度为 1。
· maxDepth(node) 返回以 node 为根的子树最大深度。
· 每个节点向父节点汇报：1 + max(左子树深度, 右子树深度)。

maxDepth 三步骤

root == nil → 0
left = maxDepth(root.Left)
right = maxDepth(root.Right)
return 1 + max(left, right)

递归调用栈：子树先汇报，父节点再汇总

1.maxDepth(node) 压栈后，先递归 left = maxDepth(root.Left)。
2.左子树返回深度后，再递归 right = maxDepth(root.Right)。
3.子节点用气泡向父节点返回 1 + max(left, right)，栈逐层弹出。

1/8 · 题目定义

8 步分镜：

Step 1题目定义

题目定义：最大深度数节点，不数边

给定一棵二叉树，求最大深度。LeetCode 104 的定义是：从根节点到最远叶子节点路径上的节点数。示例树最长路径 3 → 20 → 15，经过 3 个节点，所以最大深度是 3——不是 2 条边。空树深度为 0，单节点树深度为 1。

最大深度 = 从根节点到最远叶子节点路径上的节点数（数节点，不数边）。
最大深度 = 根到最远叶子路径上的节点数，不是边数。
空树深度为 0，单节点树深度为 1。
maxDepth(node) 返回以 node 为根的子树最大深度。
每个节点向父节点汇报：1 + max(左子树深度, 右子树深度)。

为什么正确

最大深度 = 从根节点到最远叶子节点路径上的节点数（数节点，不数边）。

状态表 · 当前发生了什么

当前节点	调用栈	本层返回值	机器状态
—	[]	—	读题定义 · 示例树

公式计算过程

最长路径：3 → 20 → 15

节点数 = 3（不是边数 2）

高度汇报实验室·高亮 = 当前访问节点·气泡 = 子树深度返回值

递归栈 · 当前调用链

（空栈 · 递归完成）

Go · maxDepth

1func maxDepth(root *TreeNode) int {
2    if root == nil {
3        return 0
4    }
6    left := maxDepth(root.Left)
7    right := maxDepth(root.Right)
9    if left > right {
10        return left + 1
11    }
12    return right + 1
13}

复杂度

时间: O(n)
空间: O(h)

每个节点访问一次，n 为节点总数。

h 为树高。递归栈深度等于树高：平衡树约 O(log n)，最坏单链退化 O(n)。不是 O(1) · 最坏 O(n)

面试回答

定义 maxDepth(node) 表示以当前节点为根的子树最大深度。空节点返回 0；非空节点分别递归求左右子树深度，然后返回 1 + max(left, right)。每个节点访问一次，时间复杂度 O(n)。递归栈高度等于树高，空间复杂度 O(h)，最坏 O(n)，平衡树 O(log n)。

常见误区

误区 1：最大深度数边，不是数节点

LeetCode 104 定义的是路径上的节点数。例：3→20→15 共 3 个节点，深度是 3 不是 2。

误区 2：空节点深度写成 -1

空树没有节点，深度为 0。递归基 if root == nil { return 0 } 是标准写法。

误区 3：单节点树深度写成 0

只有一个根节点时，路径上只有 1 个节点，深度为 1。

误区 4：空间复杂度写成 O(1)

递归 DFS 需要系统调用栈保存暂停状态，空间是 O(h)，不是 O(1)。

误区 5：单链树栈深度退化

若树退化为链表，递归栈深度为 n，空间最坏 O(n)。

迁移练习

LC111 · 最小深度

不能简单 min(left, right)，因为空子树不能算有效路径，需单独处理。

LC110 · 平衡二叉树

每个节点也要拿左右子树高度，但判断条件是 |left − right| ≤ 1。

LC543 · 二叉树直径

同样依赖左右子树高度，但答案是 left + right（经过该节点的最长路径）。