算法 - 二叉树的最大深度

Posted on

1. 题目

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
        3
       / \
      9   20
         /  \
        15   7

输入: root = [3, 9, 20, null, null, 15, 7]
输出: 3   （最长路径 3 -> 20 -> 15 或 3 -> 20 -> 7，共 3 个节点）

输入: root = []
输出: 0

节点定义：

1
2
3
4
5
6
7
8
9
10
class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}

2. 解题思路

2.1 DFS 递归（最直观）

最大深度满足递归定义：

1
2
depth(node) = 1 + max(depth(node.left), depth(node.right))
depth(null) = 0

即：当前节点深度 = 左右子树更深的那个 + 1（加自己这一层）。这是典型的「把子问题答案直接组合」的递归。

  • 时间复杂度：O(n)，每个节点访问一次。
  • 空间复杂度：O(h)，递归栈，最坏 O(n)（退化成链表）。

2.2 BFS 层序

按层遍历，遍历到第几层，深度就是几。用队列 + for 循环固定「一层」的节点数，每处理完一层 depth++。适合顺带求最小深度、按层输出等变体。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// DFS 递归
function maxDepth(root: TreeNode | null): number {
    if (root === null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// BFS 层序
function maxDepthBFS(root: TreeNode | null): number {
    if (root === null) return 0;

    const queue: TreeNode[] = [root];
    let depth = 0;

    while (queue.length > 0) {
        const levelSize = queue.length; // 锁定当前层节点数
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        depth++; // 完成一层
    }

    return depth;
}

4. 面试延伸

  • 最小深度（111 题） 的坑：只有一个孩子时，不能简单 min(左, 右)，要排除值为 0 的那侧空子树。
  • 平衡二叉树判断（110 题）：DFS 求深度时顺带检查任意节点左右子树高度差 ≤ 1，用「自底向上 + 提前终止（返回 -1 作标记）」优化到 O(n)。
  • 树的直径（543 题）：求任意两点最长路径，需要在全局记录 左高 + 右高 的最大值，是最大深度的高频变体。
  • 递归三要素：明确返回值含义、写好 base case（null -> 0）、信任递归不需要手动展开。

难度：简单 | LeetCode 104 题 | 二叉树递归入门