一、题目描述

104. 二叉树的最大深度

给定一个二叉树 root，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

• 树中节点的数量在 [0, 10⁴] 范围内

• -100 <= Node.val <= 100

二、解题思路概览

求二叉树的最大深度，本质上是求树的高度。常见解法有三种：

解法	时间复杂度	空间复杂度	特点	面试推荐
递归（DFS）	O(n)	O(n) (最坏)	代码最简洁，一行搞定	⭐⭐⭐⭐⭐
迭代（BFS层序遍历）	O(n)	O(n)	直观，能同时得到每层信息	⭐⭐⭐⭐
迭代（DFS栈）	O(n)	O(n)	模拟递归，不用递归栈	⭐⭐⭐

三、解法一：递归（DFS）⭐

3.1 核心思路

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

这是一个标准的递归定义：

• 递归终止条件：节点为 null 时，深度为 0

• 递归公式：depth(root) = 1 + max(depth(root.left), depth(root.right))

3.2 代码实现

java

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

3.3 图解示例

以 root = [3,9,20,null,null,15,7] 为例：

text

        3
       / \
      9  20
         / \
        15 7

递归调用过程：

text

maxDepth(3)
  ├─ leftDepth = maxDepth(9)
  │   ├─ leftDepth = maxDepth(null) = 0
  │   ├─ rightDepth = maxDepth(null) = 0
  │   └─ return 1 + max(0,0) = 1
  ├─ rightDepth = maxDepth(20)
  │   ├─ leftDepth = maxDepth(15)
  │   │   ├─ leftDepth = maxDepth(null) = 0
  │   │   ├─ rightDepth = maxDepth(null) = 0
  │   │   └─ return 1 + max(0,0) = 1
  │   ├─ rightDepth = maxDepth(7)
  │   │   ├─ leftDepth = maxDepth(null) = 0
  │   │   ├─ rightDepth = maxDepth(null) = 0
  │   │   └─ return 1 + max(0,0) = 1
  │   └─ return 1 + max(1,1) = 2
  └─ return 1 + max(1,2) = 3

3.4 极简写法（一行代码）

java

class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

3.5 复杂度分析

• 时间复杂度：O(n)，每个节点恰好被访问一次

• 空间复杂度：O(n)，最坏情况下（单链表树）递归栈深度为 n

四、解法二：迭代（BFS层序遍历）⭐⭐⭐⭐

4.1 核心思路

使用队列进行层序遍历：

1. 每遍历一层，深度加 1

2. 将当前层的所有节点的左右子节点加入队列

3. 重复直到队列为空

这种方法更直观：树的深度 = 层数。

4.2 代码实现

java

import java.util.*;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int levelSize = queue.size();
            
            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;  // 一层遍历完，深度加1
        }
        return depth;
    }
}

4.3 图解示例

以 root = [3,9,20,null,null,15,7] 为例：

text

初始: queue = [3], depth = 0

第1层: levelSize = 1
  取出3，加入9和20 → queue = [9,20]
  depth = 1

第2层: levelSize = 2
  取出9（无子节点）
  取出20，加入15和7 → queue = [15,7]
  depth = 2

第3层: levelSize = 2
  取出15（无子节点）
  取出7（无子节点）
  depth = 3

队列为空，结束，返回 depth = 3

4.4 复杂度分析

• 时间复杂度：O(n)，每个节点入队出队各一次

• 空间复杂度：O(n)，队列最多存储一层的节点（最坏情况是满二叉树的最后一层，约 n/2 个节点）

五、解法三：迭代（DFS栈）

5.1 核心思路

使用栈模拟递归的 DFS 过程，同时记录每个节点对应的深度。当访问到叶子节点时，更新最大深度。

5.2 代码实现

java

import java.util.*;

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        
        Deque<TreeNode> stack = new ArrayDeque<>();
        Deque<Integer> depthStack = new ArrayDeque<>();
        stack.push(root);
        depthStack.push(1);
        int maxDepth = 0;
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int depth = depthStack.pop();
            
            maxDepth = Math.max(maxDepth, depth);
            
            // 先右后左，顺序无所谓，因为只是求深度
            if (node.right != null) {
                stack.push(node.right);
                depthStack.push(depth + 1);
            }
            if (node.left != null) {
                stack.push(node.left);
                depthStack.push(depth + 1);
            }
        }
        return maxDepth;
    }
}

5.3 复杂度分析

• 时间复杂度：O(n)

• 空间复杂度：O(n)

六、解法对比与总结

方法	时间复杂度	空间复杂度	代码复杂度	适用场景
递归 DFS	O(n)	O(n)	极简	标准答案，面试首选
迭代 BFS	O(n)	O(n)	中等	需要同时知道每层信息时
迭代 DFS	O(n)	O(n)	中等	不想用递归时

七、面试建议

7.1 应该用哪个？

场景	推荐解法
面试标准答案	递归 DFS（三行代码，简洁优雅）
被问“能否用迭代实现”	BFS 层序遍历 或 DFS 栈
需要同时获取每层信息	BFS 层序遍历

7.2 常见错误

1. 递归解法：

   • 忘记处理 root == null 的情况

   • 写成 1 + leftDepth + rightDepth（这会变成节点数总和，不是深度）

   • 递归深度过大导致栈溢出？题目限制 10⁴ 节点，最坏情况深度 10⁴，一般不会栈溢出

2. BFS 解法：

   • 忘记在循环内用变量保存 queue.size()（因为 size 会变化）

   • 深度增加的位置放错

7.3 扩展问题

Q：如果是 N 叉树的最大深度？

java

class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int maxChildDepth = 0;
        for (Node child : root.children) {
            maxChildDepth = Math.max(maxChildDepth, maxDepth(child));
        }
        return 1 + maxChildDepth;
    }
}

Q：如何求最小深度（根到最近叶子节点的距离）？

A：BFS 层序遍历，找到第一个叶子节点时返回当前深度。不能用简单的 1 + min(left, right)，因为如果某子树为空，空子树的深度 0 会导致错误结果。

八、相关链接

• 题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）

• 官方题解：二叉树的最大深度官方题解