LeetCode 104. 二叉树的最大深度
题目描述
题意分析
最大深度是从根节点到最远叶子节点的路径所包含的节点数量。空树深度为
0，只有根节点时深度为1；计算的是节点数，不是边数。一条从根向下的路径每次只能选择左、右子树中的一侧，不能同时经过两边。因此只需分别求出左右子树的最大深度，取较大者，再加上当前根节点这一层。下面先给出递归写法，再说明通过临时连接实现常数额外空间的 Morris 遍历。
解法：递归计算左右子树深度
核心思路
[!blue]
先约定递归函数
maxDepth(root)返回“以当前节点为根的子树有多高”，而不是从整棵树的根走到当前位置已经经过多少层。返回值只由当前子树决定，父节点可以直接使用它。当前节点为空时，这棵子树没有节点，返回
0。否则分别递归得到左子树高度leftDepth和右子树高度rightDepth。从当前节点出发的最长向下路径，必然选择两者中更深的一侧，再经过当前节点，所以返回max(leftDepth, rightDepth) + 1。为什么取最大值而不是相加？两边相加会把左右两条不同路径拼到一起，而根到叶子的路径只能往一侧继续。只取其中一侧又可能漏掉另一边更深的叶子，所以两个子树都必须计算。
叶子的两个孩子都为空，按这个规则自然得到
1；只有一个孩子时，空侧贡献0，较深的真实子树会被选中，无需额外分支。每层等待孩子先返回结果再计算自身，最终根节点收到的值就是整棵树的最大深度。
解题步骤
- 当前节点为空时返回
0。- 递归计算左子树与右子树的最大深度。
- 取两个结果中的较大值并加
1，计入当前节点这一层。- 从整棵树的根调用，返回值即为答案。
代码实现
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
// 取较深的一侧，再计入当前根节点这一层。
return Math.max(leftDepth, rightDepth) + 1;
}
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
leftDepth := maxDepth(root.Left)
rightDepth := maxDepth(root.Right)
// 取较深的一侧，再计入当前根节点这一层。
if leftDepth > rightDepth {
return leftDepth + 1
}
return rightDepth + 1
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次。
- 空间复杂度：$O(h)$，递归栈深度等于树高
h；树退化成链时最坏为 $O(n)$，完全平衡时为 $O(\log n)$。
关键点总结
[!green]
- 递归函数返回当前子树的最大深度。
- 空节点返回
0，叶子节点自然得到1。- 左右子树都要计算，最长路径可能位于任意一侧。
解法二：Morris 遍历
核心思路
[!blue]
递归需要调用栈保存“左子树处理完后回到哪里”。Morris 遍历利用原树中本来为空的右指针临时保存返回路线，从而不用显式栈。它适合允许遍历期间临时修改指针、又要求常数额外空间的情况；遍历结束必须恢复原树。
对当前节点
cur，如果有左子树，就从cur.left沿右指针找到最右节点pred。它是当前节点的中序前驱。第一次到达cur时，pred.right为空，将其临时设为cur，然后进入左子树。左子树处理完后会沿这条线索回到cur，再次寻找前驱时就会发现pred.right == cur，据此区分首次到达和返回。
depth需要与这两种到达方式分别配合。第一次到达一个节点之前，它保存的是这个节点上一层的深度，因此先加一，就得到当前节点的真实深度，并用它更新best。没有左孩子时无需建立线索，记录后直接沿右指针继续；有左孩子且首次到达时，记录后建立线索并向左走。沿线索返回时，
depth仍是前驱pred的真实深度，不能把这次回到cur当成又向下走了一层。寻找前驱时用steps记录从cur先向左、再沿右边界到达pred的边数：先走到左孩子算一步，之后每向右移动一次再加一。因此前驱比当前节点深
steps层。第二次到达cur时，先把pred.right恢复为空，再执行depth -= steps，就把深度恢复到cur所在层，然后进入原右子树。右子树节点首次被处理时再加一，深度衔接便与真正的树路径一致。只有首次到达时才更新
best，临时返回路线不参与最大深度计算。每个节点都会在首次到达时记录自己的真实深度，因此最大值不会遗漏；同时每条建立的线索都会在第二次到达对应节点时被拆除，完整遍历后原树结构恢复。
解题步骤
- 初始化
cur = root、depth = 0、best = 0。- 若
cur没有左孩子，将depth加一并更新best，然后沿右指针继续。- 若有左孩子，寻找中序前驱
pred，同时用steps统计从cur到它的左转后右行路径长度；遇到空右指针或指回cur的线索就停止。- 若
pred.right为空，说明首次到达：增加并记录深度，建立pred.right = cur，再进入左子树。- 否则说明左子树已处理完：拆除线索，执行
depth -= steps，再进入右子树，不重复增加深度。- 直到
cur为空，返回best；空树不进入循环，返回0。
代码实现
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public int maxDepth(TreeNode root) {
int depth = 0;
int best = 0;
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) {
depth++;
best = Math.max(best, depth);
cur = cur.right;
} else {
TreeNode pred = cur.left;
int steps = 1;
while (pred.right != null && pred.right != cur) {
pred = pred.right;
steps++;
}
if (pred.right == null) {
depth++;
best = Math.max(best, depth);
pred.right = cur;
cur = cur.left;
} else {
pred.right = null;
depth -= steps;
cur = cur.right;
}
}
}
return best;
}
}
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func maxDepth(root *TreeNode) int {
depth, best := 0, 0
cur := root
for cur != nil {
if cur.Left == nil {
depth++
best = max(best, depth)
cur = cur.Right
} else {
pred := cur.Left
steps := 1
for pred.Right != nil && pred.Right != cur {
pred = pred.Right
steps++
}
if pred.Right == nil {
depth++
best = max(best, depth)
pred.Right = cur
cur = cur.Left
} else {
pred.Right = nil
depth -= steps
cur = cur.Right
}
}
}
return best
}
复杂度分析
- 时间复杂度：$O(n)$，节点只会首次到达或沿线索返回，寻找前驱的各条右边界也只被常数次扫描，嵌套循环的总工作量为线性。
- 空间复杂度：$O(1)$，只使用固定数量的指针和计数器，临时线索占用原节点中本来为空的指针位置。
关键点总结
[!green]
- 两次到达含义不同：首次到达计入当前层并更新答案，沿线索返回只恢复深度，不重复计层。
steps是真实路径边数：初始为1，已经计入从当前节点到左孩子的那一步。- 线索必须恢复：拆除时令
pred.right = null，不能在仍有临时连接时提前结束，否则会改变原树。
易错点总结
[!yellow]
- 忘记空节点判断会触发空指针错误。
- 返回值漏掉
+1，会少算当前节点这一层。- 只递归一侧会漏掉另一侧的更深路径。
- 最大深度按节点数计算，单节点树的深度是
1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 111. 二叉树的最小深度 | 简单 | 最大深度在两侧取最大值，最小深度必须走到真实叶子，不能把缺失孩子当零深度路径。 |
| 110. 平衡二叉树 | 简单 | 复用后序求高度，并在每个节点检查左右高度差。 |
| 543. 二叉树的直径 | 简单 | 后序返回子树高度并在根处合并信息；本题取两侧最大高度加一，该题合并左右向下路径得到直径。 |
| 124. 二叉树中的最大路径和 | 困难 | 后序返回子树高度并在根处合并信息；本题取两侧最大高度加一，该题舍弃负贡献后合并最大路径和。 |
| 687. 最长同值路径 | 中等 | 后序返回子树高度并在根处合并信息；本题取两侧最大高度加一，该题仅连接值相同的向下链。 |