leetcode 仓库 104 题解:二叉树最大深度的递归 DFS 与 BFS 层次遍历双解法
leetcode 仓库 104 题解:二叉树最大深度的递归 DFS 与 BFS 层次遍历双解法
本篇基于 leetcode 题解仓库中 104. Maximum Depth of Binary Tree 的题解文档展开,完整覆盖题目描述、递归与迭代两条解题路线,以及仓库中给出的 JS、C++、Java、Python、Go、PHP 六种语言的 BFS 实现。读完你可以掌握:如何用递归一行核心逻辑求出树的深度;如何在层次遍历(BFS)中正确识别“一层结束”这一关键问题,并理解两种分层技巧(null 分隔符与当前层长度快照)的差异与陷阱。
题目描述
给定一个二叉树,找出其最大深度。
- 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数;
- 叶子节点是指没有子节点的节点。
示例:给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3。
题目原始出处为 LeetCode 第 104 题,仓库中的对应中文题解见 104. 二叉树的最大深度。根据题解文档的记录,这道题曾出现在阿里、腾讯、百度、字节,以及 Apple、LinkedIn、Uber、Yahoo 等公司的面试中,属于二叉树入门题里出现频率很高的一道。
前置知识
解这道题只需要两个前置概念:
- 递归:树本身是递归定义的数据结构,递归是处理树形结构最自然的思维方式;
- 队列与层次遍历(BFS):BFS 按层扩展节点,是迭代求深度的基础。仓库的二叉树遍历专题对前、中、后序遍历和层次遍历做了系统总结,其中明确指出:“层次遍历就是 BFS 的副产物”,BFS 的关键点在于“如何记录每一层次是否遍历完成,我们可以用一个标识位来表示当前层的结束”——这正是 104 题迭代解法的全部核心。
解法一:递归 DFS,三行核心代码
树是一种递归的数据结构,用递归解决这类问题往往非常容易,104 题恰巧也是如此。递归式定义是:
以
root为根的子树最大深度 =1 + max(左子树最大深度, 右子树最大深度)
仓库题解中的递归实现(JS):
var maxDepth = function (root) {
if (!root) return 0;
if (!root.left && !root.right) return 1;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
逐行解读:
if (!root) return 0:空树深度为 0,这是递归的终止条件(base case);if (!root.left && !root.right) return 1:叶子节点深度为 1。从源码结构看,这一行其实是冗余的——对叶子节点走第三行同样得到1 + Math.max(0, 0) = 1,这里保留它只是把“叶子深度为 1”这层语义写得更直白;return 1 + Math.max(...):当前节点自身贡献 1 层,深度取决于左右子树中更深的那一侧。
递归解法天然利用了树的后序思想:先得到左右子树的答案,再汇总到当前层。每个节点恰好访问一次,因此时间复杂度为 O(N);最坏情况下(退化为链状树)递归调用栈深度为 O(N)。
解法二:迭代 BFS,关键在于“如何划分每一层”
如果使用迭代?题解的思路是:首先想到树的各种遍历,由于求的是深度,层次遍历(BFS)非常合适,只需要记录有多少层即可。
把 BFS 变成“按层遍历”,有且仅有两种主流技巧,仓库的六份代码里恰好两种都用到了:
| 技巧 | 做法 | 仓库中使用该技巧的语言 |
|---|---|---|
null 分隔符 |
队列中每层末尾插入一个特殊元素 null,出队到 null 即表示本层结束 |
JS、Python、Go、PHP |
| 当前层长度快照 | 每轮循环开始时记录 queue.size(),本轮恰好处理这么多个节点,即一整层 |
C++、Java |
下面先讲 null 分隔符法,因为它是仓库 JS 主实现采用的方式。
技巧一:null 分隔符法(以 JS 实现为例)
仓库的完整 JS 题解:
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function (root) {
if (!root) return 0;
if (!root.left && !root.right) return 1;
// 层次遍历 BFS
let cur = root;
const queue = [root, null];
let depth = 1;
while ((cur = queue.shift()) !== undefined) {
if (cur === null) {
// 注意⚠️:不处理会无限循环,进而堆栈溢出
if (queue.length === 0) return depth;
depth++;
queue.push(null);
continue;
}
const l = cur.left;
const r = cur.right;
if (l) queue.push(l);
if (r) queue.push(r);
}
return depth;
};
算法骨架:
- 初始队列放入
[root, null],null是第 1 层的“结束标记”,此时depth = 1; - 循环弹出队首
cur; - 若
cur是null:说明刚扫完一层。此时必须区分两种情况——- 队列已空:最后一层的结束标记已出队,遍历完成,直接返回
depth(题解特别注释:不处理会无限循环,进而堆栈溢出,因为shift()之后若再无元素,循环条件会因undefined退出,但中间多推的null会造成多算一层); - 队列非空:说明后面还有下一层,
depth++,并重新推入一个null作为新层的结束标记;
- 队列已空:最后一层的结束标记已出队,遍历完成,直接返回
- 否则
cur是普通节点,把非空的left、right依次入队,等待下一轮访问。
用示例树 [3,9,20,null,null,15,7] 逐步执行一遍,可以看清整个状态变迁:
| 步骤 | 出队元素 | 动作 | 出队后队列状态 | depth |
|---|---|---|---|---|
| 1 | 3 |
入队 9、20 | [null, 9, 20] |
1 |
| 2 | null |
队列非空,depth++,补 null |
[9, 20, null] |
2 |
| 3 | 9 |
无子节点 | [20, null] |
2 |
| 4 | 20 |
入队 15、7 | [null, 15, 7] |
2 |
| 5 | null |
队列非空,depth++,补 null |
[15, 7, null] |
3 |
| 6 | 15 |
无子节点 | [7, null] |
3 |
| 7 | 7 |
无子节点 | [null] |
3 |
| 8 | null |
队列为空,返回 depth | [] |
3 |
另一个值得注意的细节:循环条件 while ((cur = queue.shift()) !== undefined) 用 undefined 而非 null 作为终止判断,是因为 Array.prototype.shift() 在队列耗尽时返回 undefined,而 null 是算法主动放入的分隔符,两者必须区分开。
技巧二:当前层长度快照法(以 Java 实现为例)
不需要向队列里塞特殊元素。每轮 while 迭代开始时,先对 queue.size() 拍一个快照——此刻队列里恰好是“一整层”的节点;然后内层循环恰好弹出这么多节点,并把它们的子节点全部压入队列,供下一轮使用。弹出完毕即一整层处理完,层计数加一。
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 队列
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int res = 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;
}
// 统计层数
res += 1;
}
return res;
}
两种技巧的对比:
null分隔符法:一次线性扫描即可完成,不需要维护“本轮处理几个”的计数,但必须正确处理“最后一个null出队且队列为空”的边界,否则会多算一层甚至死循环;- 长度快照法:逻辑更直白、没有特殊元素,天然不会出界,但每层多一次
size()读取与内层循环;另外在 JS 中用数组模拟队列时,shift()是O(N)操作,若数据量较大应考虑指针下标或LinkedList。
六语言完整实现
仓库题解给出了 6 种语言的实现,语言支持:JS、C++、Java、Python、Go、PHP。下面按仓库原文收录(节点定义以各语言在 LeetCode 上的标准 TreeNode 为准)。
JS(BFS,null 分隔符)
见上文“技巧一”完整代码。
C++(BFS,长度快照)
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
auto q = vector<TreeNode*>();
auto d = 0;
q.push_back(root);
while (!q.empty())
{
++d;
auto sz = q.size();
for (auto i = 0; i < sz; ++i)
{
auto t = q.front();
q.erase(q.begin());
if (t->left != nullptr) q.push_back(t->left);
if (t->right != nullptr) q.push_back(t->right);
}
}
return d;
}
};
从源码结构看,这份 C++ 实现用 vector<TreeNode*> 充当队列,每弹出一个节点执行一次 q.erase(q.begin()),单次是 O(N) 操作,最坏整体退化为 O(N^2);在生产代码中通常应改用 std::queue / std::deque 获得摊还 O(1) 的弹出,仓库里这样写主要是为了直观展示“长度快照”这一层控制逻辑。
Java(BFS,长度快照)
见上文“技巧二”完整代码。
Python(BFS,null 分隔符)
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
q, depth = [root, None], 1
while q:
node = q.pop(0)
if node:
if node.left: q.append(node.left)
if node.right: q.append(node.right)
elif q:
q.append(None)
depth += 1
return depth
这里 elif q: 的判断与 JS 版本中的 if (queue.length === 0) return depth 完全同构:只有当队列里还有元素时才补 None 并计数,否则最后一个分隔符弹出后直接结束循环。
Go(BFS,null 分隔符)
// BFS
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
depth := 1
q := []*TreeNode{root, nil} // queue
var node *TreeNode
for len(q) > 0 {
node, q = q[0], q[1:] // pop
if node != nil {
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
} else if len(q) > 0 { // 注意要判断队列是否只有一个 nil
q = append(q, nil)
depth++
}
}
return depth
}
Go 版用切片模拟队列,node, q = q[0], q[1:] 是一次性的“取首元素并截断”出队操作;注释中特意提醒“要判断队列是否只有一个 nil”,即 else if len(q) > 0 分支的必要性——队尾只剩最后一个分隔符时不能再追加,否则 depth 会多算一层。
PHP(BFS,null 分隔符)
class Solution
{
/**
* @param TreeNode $root
* @return Integer
*/
function maxDepth($root)
{
if (!$root) return 0;
$depth = 1;
$arr = [$root, null];
while ($arr) {
/** @var TreeNode $node */
$node = array_shift($arr);
if ($node) {
if ($node->left) array_push($arr, $node->left);
if ($node->right) array_push($arr, $node->right);
} elseif ($arr) {
$depth++;
array_push($arr, null);
}
}
return $depth;
}
}
可以看到 JS、Python、Go、PHP 四个版本共享同一个算法模板:[root, null] 起步 → 弹出普通节点则入队子节点 → 弹出分隔符则(队列非空时)计数并补分隔符;C++ 与 Java 版本则采用“长度快照”模板。
复杂度分析
题解文档给出的复杂度结论:
- 时间复杂度:
O(N)——每个节点最多入队、出队一次,N为节点总数; - 空间复杂度:
O(N)——最坏情况下(如完全二叉树的最后一层)队列中同时存放约N/2个节点;递归解法的调用栈最坏也是O(N)(树退化为链时)。
相关题目与延伸
掌握“按层遍历 + 层计数”这一模式后,以下仓库内题解可以顺势打通:
- 102. 二叉树的层序遍历:把“数层”换成“收集每层节点值”,是同一套 BFS 骨架的直接应用,同样给出了
null分隔符与长度快照两种写法; - 103. 二叉树的锯齿形层序遍历:在 102 的基础上按奇偶层翻转输出方向;
- 二叉树遍历专题:前、中、后序(DFS)与层次遍历(BFS)的系统总结,其中“用标识位表示当前层结束”的表述即 104 题迭代解法的理论出处;
- 递归思想的更多练习可参考仓库的动态规划思考等专题文档。
一句话总结:104 题的价值不在于它本身多难,而在于它把“树的深度 = 最长路径节点数”这个问题,同时演示了树问题的两大通用解法——**递归(子问题最优解自底向上汇总)**与 BFS(按层扩展 + 层边界识别),两者都是后续所有树形题的公共构件。