二叉树的最大深度
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个二叉树 root，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数（边数 + 1）。
树中节点数目在 [0, 104] 内，节点值在 [-100, 100] 范围内。
示例 1
示例 2
示例 3
模拟答题者思考
1. 暴力直觉：从根出发枚举所有根到叶子的路径，记录路径上节点个数取最大——正确但会重复遍历共享前缀，时间可退化到 O(n²)。
2. 重复在哪里？「整棵树的最大深度」只依赖「左子树有多深、右子树有多深」——子问题与整题同型，且每个节点只需汇总一次左右结果。
3. 后序递归：空节点返回 0；非空节点深度 = 1 + max(左, 右)。示例 1：左子树 9 为叶子深度 1，右子树 20 下最深 15/7 深度 2，根得 1+max(1,2)=3。
4. BFS 等价视角：按层扩展队列，每处理完一层 depth++，最后 depth 即最大深度（与 DFS 同 O(n)）。
5. 每个节点访问常数次，时间 O(n)；递归栈深度 O(h)，链状树最坏 O(n)。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
root | TreeNode* | 定义：当前子树的根，整题从全局根开始向下递归 维护：每次调用只关心「以 root 为根的子树有多深」 更新：处理完当前节点后， root 在调用栈中变为父节点传下来的左/右孩子 |
maxDepth(root) | int | 定义：子树 root 的最大深度；空树深度为 0维护：真值 = 1 + max(左子树深度, 右子树深度)；叶子左右皆空时子树深度为 1 更新： return 1 + max(dfs(left), dfs(right))，基线 if (!root) return 0 |
depth（BFS） | int | 定义：层序遍历时当前已完成的层数（根在第 1 层） 维护：每轮按 size 清空一层队列后 depth += 1更新：队列为空时 depth 即为答案 |
落码步骤
1. 若 root 为空，返回 0
2. 递归求 left = maxDepth(root.left)，right = maxDepth(root.right)
3. 返回 1 + max(left, right)
4. （BFS 备选）队列入根，depth = 0；非空则按层 size 弹出、孩子入队，每层结束 depth += 1
代码实现
class Solution:
def maxDepth(self, root: TreeNode | None) -> int:
if not root:
return 0
return 1 + max(
self.maxDepth(root.left),
self.maxDepth(root.right),
)
# BFS 层数写法：
# from collections import deque
# def maxDepth(self, root):
# if not root: return 0
# q = deque([root]); depth = 0
# while q:
# for _ in range(len(q)):
# node = q.popleft()
# if node.left: q.append(node.left)
# if node.right: q.append(node.right)
# depth += 1
# return depthclass Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}
};
// 时间 O(n)，空间 O(h)复杂度分析
O(n)
O(h)（递归栈，h 为树高；BFS 队列最坏 O(n)）
常见坑
空树返回 1：题目规定空树深度为 0，基线必须是 if (!root) return 0。
把「深度」当成边数：题意是节点个数，叶子一层要 +1，不能写成 max(left, right) 而不加当前层。
与 #111「最小深度」混淆：最小深度要到叶子；最大深度只需看更深的一侧，空子树在 max 里贡献 0 即可。
必测边界 Case
root = [] → 0
root = [1] → 1
root = [1,null,2] → 2
root = [3,9,20,null,null,15,7] → 3
n 个节点一条链 → 深度 n（验证栈深度与返回值）