LeetCode 剑指 Offer 55 - I. 二叉树的深度
题目描述
题意分析
二叉树的深度，是从根到最远叶子的一条路径上包含的节点数量。只比较一条路径能有多长，不是统计整棵树有多少个节点。
空树没有节点，深度为零；只有根节点时深度为一。题目计算最大深度，所以有一个孩子缺失时，仍应沿存在且更深的分支计算。
解法：后序递归求树高
核心思路
[!blue]
定义递归返回值为“以当前节点为根的这棵子树有多深”，而不是从最初根节点已经走过了几层。这样父节点只需读取左右孩子各自的答案，就能得到自己的答案。
对非空节点，从它出发的最长根到叶路径，下一步必然进入左子树或右子树，因此应选择更深的一侧，再加上当前节点这一层：
max(left, right) + 1。两边的深度不能相加，因为一条向下路径无法同时走进两棵子树。空节点返回零，递归由此终止。叶子的两个孩子都为空，自然得到深度一；只有一个孩子时，另一边的零不会超过真实路径，也不需要额外区分。
先递归取得左右子树结果，再计算当前节点，属于后序处理。每个节点只计算一次，子树的正确结果逐层组合成整棵树的深度。
解题步骤
- 当前节点为空时返回
0。- 递归计算左子树深度
left和右子树深度right。- 返回
max(left, right) + 1，把当前节点这一层计入。- 最外层递归返回的值就是整棵树的深度。
代码实现
class Solution {
// 空节点没有层数，递归边界返回 0。
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
// 选择较深的一侧，再计入当前节点这一层。
return Math.max(left, right) + 1;
}
}
// 返回当前子树的节点层数：空树为零，非空为较高孩子高度加一。
func maxDepth(root *TreeNode) int {
// 空节点没有层数，递归边界返回 0。
if root == nil {
return 0
}
left := maxDepth(root.Left)
right := maxDepth(root.Right)
// 选择较深的一侧，再计入当前节点这一层。
if left > right {
return left + 1
}
return right + 1
}
复杂度分析
设节点数为 $n$，树高为 $h$。
- 时间复杂度：$O(n)$，每个节点访问一次并进行常数次计算。
- 辅助空间复杂度：$O(h)$，用于递归调用栈；退化为单链时为 $O(n)$。
关键点总结
[!green]
- 递归返回当前子树的高度，父节点据此选择更深的分支。
- 最大深度取左右最大值，当前非空节点再贡献一层。
- 空节点返回零，叶子和单孩子节点都自然覆盖。
易错点总结
[!yellow]
- 把左右结果相加会统计两边分支，不再表示一条最长路径。
- 只返回左右最大值而不加一，会漏掉当前节点这一层。
- 空树应返回零，不能与单节点树混为一谈。
- 同时传入沿途层数又在返回时逐层加一，容易重复计数，应保持一个明确的返回值定义。
- 最小深度不能直接把
max换成min，因为缺失的孩子不代表通往真实叶子的路径。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 111. 二叉树的最小深度 | 简单 | 最大深度在两侧取最大值，最小深度必须走到真实叶子，不能把缺失孩子当零深度路径。 |
| 110. 平衡二叉树 | 简单 | 复用后序求高度，并在每个节点检查左右高度差。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！