#104
简单
低频
深度优先遍历二叉树的最大深度
这是一道围绕树、二叉树展开的高频练习。建议先掌握「深度优先遍历」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
题目分析
给你一棵二叉树，要求返回它的最大深度。
最大深度指的是从根节点到最远叶子节点路径上，节点的数量。
一句话概括：
一棵树的最大深度，等于左右子树最大深度中的较大值再加一。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：用递归 DFS 求左右子树深度，再返回两者较大值加上当前根节点这一层。
推荐代码
推荐解法：深度优先遍历
时间复杂度： O(n)
空间复杂度： O(h)
核心思路： 用递归 DFS 求左右子树深度，再返回两者较大值加上当前根节点这一层。
// 二叉树节点结构
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
// 计算二叉树的最大深度
public int maxDepth(TreeNode root) {
// 如果根节点为空，返回深度 0
if (root == null) {
return 0;
} else {
// 递归计算左子树的最大深度
int leftHeight = maxDepth(root.left);
// 递归计算右子树的最大深度
int rightHeight = maxDepth(root.right);
// 返回左右子树深度的较大值加 1（当前节点）
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
结构化讲解
面试时怎么讲
开场思路
这题我会直接用树递归。每个节点的最大深度，取决于左右子树里更深的那一边。
核心过程
- 定义
maxDepth(node)表示以当前节点为根的最大深度。 - 如果节点为空，返回 0，作为递归终止条件。
- 递归拿到左右子树深度后，取较大值再加上当前节点这一层。
- 最终根节点返回的值就是整棵树的最大深度。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(h)，其中 h 是树高。
面试补一句：树递归题先说清楚“函数返回什么”，通常就已经完成一半了。
核心思路
最大深度是典型的树递归题。每个节点只需要回答一个问题：以我为根的子树有多深，这正好等于左右子树最大深度再加 1。
步骤讲解
1
先定义递归函数含义
让函数 maxDepth(node) 表示以 node 为根的树的最大深度。
为什么这样做：树题递归想清楚函数语义后，转移通常会非常直接。
对应代码提示：int maxDepth(TreeNode node)
2
空节点直接返回 0
当节点为空时，说明这条路径已经结束，深度记为 0。
为什么这样做：这是递归终止条件，也是叶子节点向上回传深度的基础。
对应代码提示：if (node == null) return 0;
3
分别递归左右子树
递归计算左子树深度和右子树深度。
为什么这样做：当前节点的答案必须建立在子问题答案之上。
对应代码提示：int left = maxDepth(node.left); int right = maxDepth(node.right);
4
当前节点返回较大深度加 1
取左右子树较大值，再加上当前节点这一层。
为什么这样做：根到最深叶子的路径一定经过当前节点，所以要把自己这一层补上。
对应代码提示：return Math.max(left, right) + 1;
易错点
把空节点返回成 1
这样会导致叶子节点深度被多算一层，整体结果偏大。
正确理解：空节点代表没有层数，应该返回 0。
只累加一边深度
最大深度要看更深的那一侧，而不是固定走左边或右边。
正确理解：返回
Math.max(left, right) + 1。混淆节点数和边数
这题深度按节点层数计算，不是按边数计算。
正确理解：叶子节点的深度应该是 1，不是 0。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(h)
比其他方案更好在哪里：比按层 BFS 写法更短，也更贴合“树高”这个递归定义。
适用判断：只要题目要求树的高度、路径长度或子树属性，优先考虑 DFS 递归定义。
额外提醒
- 这题的核心不是遍历顺序，而是递归定义。
其他语言 / 其他解法
广度优先遍历
使用队列进行层序遍历，每完成一层深度加 1，直到队列为空。
广度优先遍历
使用队列进行层序遍历，每完成一层深度加 1，直到队列为空。
时间复杂度：O(n)
空间复杂度：O(n)
一句话思路：使用队列进行层序遍历，每完成一层深度加 1，直到队列为空。
// 二叉树节点结构
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
import java.util.LinkedList;
import java.util.Queue;
class Solution {
// 计算二叉树的最大深度
public int maxDepth(TreeNode root) {
// 如果根节点为空，返回深度 0
if (root == null) {
return 0;
}
// 创建队列用于广度优先遍历
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int depth = 0;
// 层序遍历
while (!queue.isEmpty()) {
// 获取当前层的节点数量
int size = queue.size();
// 处理当前层的所有节点
while (size > 0) {
TreeNode node = queue.poll();
// 将左子节点加入队列
if (node.left != null) {
queue.offer(node.left);
}
// 将右子节点加入队列
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
// 每完成一层，深度加 1
depth++;
}
return depth;
}
}
动画演示
如果你还没完全看懂，可以展开动画演示。
深度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
深度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树的结构（如：[3,9,20,null,null,15,7]），然后点击开始
广度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
广度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树的结构（如：[3,9,20,null,null,15,7]），然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。