leetcode 仓库 104 题解:二叉树最大深度的递归 DFS 与 BFS 层次遍历双解法

原创2026-09-17 10:27:161,664 阅读
文章标签:教程教育文档

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;
};

算法骨架:

  1. 初始队列放入 [root, null],null 是第 1 层的“结束标记”,此时 depth = 1;
  2. 循环弹出队首 cur;
  3. 若 cur 是 null:说明刚扫完一层。此时必须区分两种情况——
    • 队列已空:最后一层的结束标记已出队,遍历完成,直接返回 depth(题解特别注释:不处理会无限循环,进而堆栈溢出,因为 shift() 之后若再无元素,循环条件会因 undefined 退出,但中间多推的 null 会造成多算一层);
    • 队列非空:说明后面还有下一层,depth++,并重新推入一个 null 作为新层的结束标记;
  4. 否则 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(按层扩展 + 层边界识别),两者都是后续所有树形题的公共构件。

登录后查看全文
leetcode