跳至主要內容

二叉树深度——DFS递归与迭代的完整实现

老张2026/4/30大约 8 分钟

二叉树深度——DFS递归与迭代的完整实现

适读人群：Java 后端工程师、算法入门同学 | 阅读时长：约18分钟 | 难度：Easy

开篇故事

104 题（最大深度）和 111 题（最小深度）是很多人刷 LeetCode 时遇到的前几道树的题目，看起来简单，但这两道题合起来讲，有很多值得深挖的地方。

104 题一行递归就搞定，没什么好说的。但 111 题最小深度有个坑——最小深度的定义是"从根节点到最近的叶子节点的最短路径上的节点数"，叶子节点是没有子节点的节点。这里"叶子节点"的限定，让直接照搬最大深度的代码必然出错。

我见过很多人把 111 题写成：

return 1 + Math.min(minDepth(root.left), minDepth(root.right));

然后在 [1, 2]（节点 1 有左子节点 2，没有右子节点）这个用例上得到答案 1，但正确答案是 2。

为什么？因为右子树是 null，minDepth(null) 返回 0，min(minDepth(left), 0) = 0，导致深度被错误缩短了。

这个坑是真的坑，值得专门讲一讲。

一、题目解析

题目一：LeetCode 104. 二叉树的最大深度

给定一个二叉树 root，返回其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

题目二：LeetCode 111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意：叶子节点是指没有子节点的节点。

示例：

输入：root = [3,9,20,null,null,15,7]
104输出：3（最长路径 3->20->15 或 3->20->7）
111输出：2（最短路径 3->9）

输入：root = [2,null,3,null,4,null,5,null,6]
104输出：5
111输出：5（只有右子链，唯一叶子节点在末尾）

考点梳理：

  1. DFS 递归实现最大深度
  2. 最小深度的特殊处理——节点只有一个子树时不能取 min(left, right)
  3. BFS 层序遍历计算深度（对最小深度尤其高效）
  4. 迭代 DFS（用栈）

二、解法一：DFS 递归（最大深度）

思路

最大深度 = 1 + max(左子树最大深度, 右子树最大深度)

边界：空节点深度为 0。

完整代码

// 104: 最大深度
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

这是教科书级别的递归，一行代码，无可挑剔。

复杂度分析

  • 时间复杂度：O(n)。每个节点访问一次。
  • 空间复杂度：O(h)。h 为树的高度，递归调用栈深度。最坏情况（链状树）O(n)，平衡树 O(logn)。

三、解法二：DFS 递归（最小深度的正确写法）

思路

最小深度不是简单的 1 + min(left, right)，因为这对只有一个子树的节点（叶子节点的父节点）会产生错误结果。

正确逻辑：

  • 如果节点只有右子树（左子树为 null），那么最小深度来自右子树，不能取 min(0, rightDepth) = 0
  • 如果节点只有左子树，同理
  • 只有当节点同时有左右子树时，才取两者的最小值

完整代码

// 111: 最小深度（正确写法）
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        
        // 只有右子树：最小深度只能来自右子树
        if (root.left == null) return 1 + minDepth(root.right);
        
        // 只有左子树：最小深度只能来自左子树
        if (root.right == null) return 1 + minDepth(root.left);
        
        // 左右子树都有：取最小值
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }
}

复杂度分析

  • 时间复杂度：O(n)。每个节点访问一次。
  • 空间复杂度：O(h)。递归栈深度为树的高度。

四、解法三：最优解法——BFS 层序遍历（最小深度最高效）

思路

对于最小深度，BFS 其实比 DFS 更高效——BFS 遇到第一个叶子节点时，就找到了最小深度，可以提前退出。DFS 必须遍历完整棵树才能确定最小深度（因为不知道右边是否还有更浅的叶子节点）。

最大深度同样可以用 BFS，遍历完所有层，最后层数就是最大深度。

Mermaid 图——BFS 最小深度提前退出

完整代码（BFS 版本，同时包含 104 和 111）

// 104: 最大深度（BFS版）
class Solution104BFS {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            depth++;  // 每处理一层，深度加1
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return depth;
    }
}

// 111: 最小深度（BFS版，遇到叶节点立即返回）
class Solution111BFS {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 遇到叶子节点，当前深度就是最小深度，提前返回
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return depth;
    }
}

// 迭代 DFS（用栈）——最大深度
class Solution104DFSIter {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
        stack.push(new Pair<>(root, 1));
        int maxDepth = 0;
        
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> pair = stack.pop();
            TreeNode node = pair.getKey();
            int depth = pair.getValue();
            
            maxDepth = Math.max(maxDepth, depth);
            
            if (node.right != null) stack.push(new Pair<>(node.right, depth + 1));
            if (node.left != null) stack.push(new Pair<>(node.left, depth + 1));
        }
        
        return maxDepth;
    }
}

复杂度分析（BFS 版本）

最大深度 BFS：

  • 时间复杂度：O(n)。遍历所有节点。
  • 空间复杂度：O(n)。队列最大存储最宽层的节点。

最小深度 BFS：

  • 时间复杂度：O(n) 最坏，但提前退出后可以显著减少实际遍历节点数。对于左右子树不平衡的树（最浅叶子在前几层），性能远好于 DFS。
  • 空间复杂度：O(n)。

提交结果（111 BFS 版）：时间击败约 98% 用户。

五、举一反三

同类题目

LeetCode 559. N叉树的最大深度 和 104 题一模一样，只不过子节点数量不限，递归时遍历所有子节点取最大深度。

LeetCode 543. 二叉树的直径 直径 = 某节点的左子树高度 + 右子树高度，依赖深度计算，但需要全局变量跟踪最大值。

LeetCode 110. 平衡二叉树 判断二叉树是否平衡：每个节点左右子树高度差不超过 1。可以在求深度的递归里附带判断平衡条件。

LeetCode 257. 二叉树的所有路径 从根到叶的所有路径，是深度计算的扩展。

最大深度与最小深度的核心区别

最大深度最小深度
递归公式1 + max(left, right)需要额外判断单子树情况
BFS 优化遍历全部层遇到叶节点即可返回
特殊节点无只有单子树的节点不能取 min

六、踩坑实录

坑一：111 题照搬 104 的递归公式

// 错误：对于节点 [1, 2]（只有左子节点），返回 min(1, 0)+1 = 1，但正确答案是 2
return 1 + Math.min(minDepth(root.left), minDepth(root.right));

null 子树的深度是 0，min(actualDepth, 0) = 0，导致深度被错误地缩短。必须单独处理只有一个子树的情况。

坑二：BFS 计算最大深度时 depth 的自增时机

// 正确：在处理每层之前先 depth++
while (!queue.isEmpty()) {
    depth++;
    int size = queue.size();
    for (...) { ... }
}

如果在处理完当前层之后再 depth++，最后一次循环（处理最后一层）结束后退出循环，但 depth 还没有自增，会导致结果少1。

坑三：迭代 DFS 里栈存储 (node, depth) 对时，Java 没有原生 Pair

Java 标准库没有 Pair 类，可以用 int[] 数组存节点和深度，或者用 AbstractMap.SimpleEntry，或者直接定义一个内部类。另一种方式是不在栈里存深度，而是用另一个栈同步记录深度。

坑四：叶节点的定义混淆

叶节点是左右子节点都为 null 的节点。有时候题目里会有只有一个子节点的节点（比如链状树），这类节点不是叶节点。在 111 题里，最小深度只统计到叶节点为止，不能把"只有一个子节点的节点"当作叶节点对待。

坑五：空树的处理

root == null 时最大深度和最小深度都应该返回 0。这行判断必须在函数最开头，否则访问 root.left 会 NPE。

七、总结

104 和 111 这两道题放在一起讲，核心是为了把"为什么最小深度不能简单用 min"说清楚。这个坑掉进去过的人都知道有多坑，理解了之后也很难再忘。

从这两道题里可以提取的思维模式是：遇到只有一个子树的节点，处理"最小值"类问题时要特别小心，不能把空子树的返回值（0 或 null）当成一个有效的参与比较的深度。

BFS 对最小深度的优化是一个很好的例子——用对了算法，不仅思路更清晰，性能也更好。当树不平衡、最浅叶子节点在前几层时，BFS 可以非常早地退出，而 DFS 无论如何都要遍历整棵树。

编辑此页
最近更新:
贡献者: xiaozhangge