LeetCode 剑指 Offer 55 - I. 二叉树的深度
目录
题目描述
题意分析
给一棵二叉树的根节点，求它的深度，也就是从根节点到最远叶子节点所经过的节点总数。
注意计量单位是「节点数」而不是「边数」。单个根节点的深度是 $1$ 而不是 $0$，这个约定决定了递归边界该返回什么。
「最远」意味着要取所有根到叶路径中最长的那一条，而不是任意一条。这一点在与最小深度那道题对照时格外重要：求最大值时可以对左右子树无差别地取较大者，求最小值时却不能，因为空子树不构成一条到叶子的路径。
树是通过节点引用给出的，不保证平衡，退化成一条链是合法输入，所以递归深度可能等于节点数。
边界只有两种：树为空时深度为 $0$；只有根节点时深度为 $1$。理想的写法应当让这两种情况都由同一条递归边界自然产生，而不是各写一个特判。
解法：后序递归求树高
核心思路
这道题的结构和树的定义几乎完全同构，所以不存在「暴力解」与「优化解」的落差，真正要想清楚的是把什么信息交给父节点。
先看一个容易走偏的方向：自顶向下地往下传当前层数，一路走到叶子再和一个全局最大值比较。这样做能得到答案，但需要维护一个跨越整棵树的可变状态，函数的返回值形同虚设，调试时也说不清某次调用到底代表什么。
换成自底向上就干净得多。一棵树的深度，等于它左子树深度和右子树深度中较大的那个，再加上根节点自己所占的这一层。这条关系是递归的：要算根就得先算两棵子树，属于典型的后序处理——先取子结果，再合成本层结果。
由此确定的递归契约是：
maxDepth(node)返回以node为根的子树的深度。这个含义在所有分支下都必须保持一致，既不能在某一支返回边数、也不能在某一支返回全局答案。边界随之被唯一确定：空节点不占任何一层，返回 $0$。这个 $0$ 不是「无效值」，而是「空树深度为零」这一事实，正因为如此，叶子节点会得到 $\max(0, 0) + 1 = 1$，与题目的计数约定自动对上。整套逻辑里不需要「判断当前节点是不是叶子」，因为叶子只是两棵子树都为空的普通情形。
解题步骤
- 若当前节点为空，返回 $0$。这是唯一的递归出口，它同时承担了两件事：终止递归，以及提供「空树深度为零」这个正确的初值。把空树判掉而不是判叶子，能让代码少一个分支。
- 递归求左子树的深度并存入变量。先存变量再使用，是为了让后面的合成语句只做比较，不掺杂副作用，读起来更接近数学定义。
- 递归求右子树的深度并存入变量。左右两次调用互不影响，顺序可以交换，这正说明该状态没有跨分支的依赖。
- 返回两者中的较大值加 $1$。加的这个 $1$ 就是当前节点自身贡献的一层，取较大值对应题目要的「最远」。
以根为
3、左子为9、右子为20、20的左右子分别为15和7的树走一遍：从根节点3进入，它非空，先去算左子树。进入节点
9：非空，先算它的左子树，得到空节点返回 $0$；再算右子树，同样返回 $0$。合成结果为 $\max(0, 0) + 1 = 1$，节点9这一支返回 $1$。回到节点
3，left得到 $1$。接着去算右子树，进入节点20：非空，先算它的左子树。进入节点
15：两个孩子都是空，各返回 $0$，合成 $\max(0, 0) + 1 = 1$，返回 $1$。回到节点20，left得到 $1$。再进入节点7：同理返回 $1$，right得到 $1$。节点20合成 $\max(1, 1) + 1 = 2$，返回 $2$。回到节点
3，right得到 $2$。合成 $\max(1, 2) + 1 = 3$，返回 $3$。核对：最长的根到叶路径是
3→20→15（或3→20→7），共 $3$ 个节点，与结果一致。再看两个边界：树为空时第一次调用就返回 $0$；只有根节点时两次子调用都返回 $0$，合成 $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
}
复杂度分析
- 时间复杂度：$O(n)$，其中 n 是节点总数。每个节点恰好被调用一次，且每次调用内部只做两次比较和一次加法，没有重复访问也没有回溯，所以总量与节点数成正比。
- 空间复杂度：$O(h)$，其中 h 是树的高度，来自递归调用栈。树平衡时 h 约为 $\log n$，退化成一条链时 h 等于 n，因此最坏情况是 $O(n)$。函数本身没有申请任何与规模相关的数据结构。
关键点总结
- 树形递归的第一件事是敲定「返回给父节点的是什么」。本题的契约是「以我为根的子树深度」，一旦这个含义在所有分支上保持一致，转移和边界都会自动浮现。
- 递归边界应当表达一个事实而不是一个哨兵。返回 $0$ 是因为空树确实没有层数，正因为它有真实含义，叶子节点才能不加特判地得到 $1$。
- 判空而不判叶子，是树题里减少分支的通用技巧。叶子只是「两个孩子都为空」的普通情形，单独为它写一支既多余又容易与空树的处理产生矛盾。
- 自底向上收集子树信息，通常优于自顶向下传递路径状态。前者靠返回值组合，函数是纯的、可独立测试；后者要维护全局可变量，容易把「当前节点的贡献」和「整棵树的答案」混为一谈。
- 面试视角：这题本身是送分题，面试官真正在看的是你会不会主动说出空间复杂度是 $O(h)$ 而不是 $O(n)$，以及最坏情况为什么退化。能补一句「链状树会栈溢出，可改用层序遍历」就足够了。
- 面试视角：高频追问是「和最小深度有什么不同」。要能指出最大深度可以无差别取 $\max$，而最小深度必须排除空子树那一侧，否则一条腿的节点会被算成深度 $1$，这是最能区分理解深浅的一问。
易错点总结
- 错误写法：递归边界返回 $-1$ → 那是按边数计量的高度约定。以只有根节点的树为例会返回 $0$，而题目要求返回 $1$，整棵树的结果会整体少 $1$。
- 错误写法：为叶子节点单独写
if (root.left == null && root.right == null) return 1;→ 逻辑上冗余，且一旦忘了保留空节点那一支，传入空树时会在访问root.left处抛空指针异常。- 错误写法：省略空节点判断，直接递归左右孩子 → 递归永不终止，第一个空孩子就会触发空指针异常或无限下探。
- 错误写法：返回
left + right + 1→ 把两棵子树的深度相加了。以根为3、左子为9、右子为20（20下再挂15和7）的树为例会返回 $1 + 2 + 1 = 4$，正确答案是 $3$。- 错误写法：把 $\max$ 写成 $\min$ → 求出的是「到最近叶子的层数」的一个错误变体。同一棵样例树会返回 $2$ 而不是 $3$，且这个值连最小深度都算不对，因为 $\min$ 会被空子树的 $0$ 带偏。
- 错误写法：用一个成员变量记录全局最大深度，递归里只更新不返回 → 函数返回值失去含义，同一个
Solution实例被连续调用两次时，上一次的残留值会污染这一次的结果。- 错误写法：先算完左右子树再对某一侧的返回值就地加一，例如
return Math.max(left + 1, right)→ 只给一侧计了当前层。样例树会返回 $\max(2, 2) = 2$，比正确答案少 $1$。- 错误写法：改用层序遍历却在同一层内逐个出队时都把层数加一 → 深度变成了节点数。必须在每轮开始时固定当前队列长度，一次性弹完这一层再累加，否则样例树会返回 $5$。
- 错误写法：认为空间复杂度是 $O(1)$ → 递归栈的深度等于树高，链状树上会退化到 $O(n)$ 并可能栈溢出，这一点在面试里被追问的频率极高。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 104. 二叉树的最大深度 | 简单 | 与本题同题，可用来对照递归写法与显式队列的层序写法 |
| 111. 二叉树的最小深度 | 简单 | 求最小值时必须排除空子树那一侧，不能直接把 $\max$ 换成 $\min$ |
| 110. 平衡二叉树 | 简单 | 在求高的同时判断左右高度差，考察如何用一个返回值携带两种信息 |
| 559. N 叉树的最大深度 | 简单 | 孩子数量不定，两次调用变成对孩子列表求最大值，边界要处理空列表 |
| 543. 二叉树的直径 | 简单 | 返回值仍是树高，但答案取自「左高加右高」，必须区分返回值与全局最优 |
| 124. 二叉树中的最大路径和 | 困难 | 同为后序合成，但子树贡献可能为负需要截断，返回值与答案分离更明显 |
| 剑指 Offer 55 - II. 平衡二叉树 | 简单 | 与 110 同题，适合练习用 $-1$ 作为「已失衡」的短路标记 |
| 面试题 04.04. 检查平衡性 | 简单 | 与 110 同题，可对比「先求高再判断」与「边求边剪枝」两种实现 |