二叉树的最大深度 - Stellar Observer Protocol

702 字

4 分钟

二叉树的最大深度

2025-08-12

Algorithms

树

/

二叉树

/

深度优先搜索

/

广度优先搜索

题目描述#

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

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

解题思路#

递归分治：
- 终止条件：节点为空时深度为0
- 递归计算左子树深度 leftDepth
- 递归计算右子树深度 rightDepth
- 当前深度 = max(leftDepth, rightDepth) + 1
迭代BFS：
- 使用队列进行层次遍历
- 每层节点遍历完成后深度+1
- 队列为空时返回累计深度
迭代DFS：
- 使用栈模拟递归
- 记录每个节点及其当前深度
- 更新全局最大深度

关键洞察#

深度递归本质：
- 任意节点深度 = 子树最大深度 + 1
- 无需重新计算相同子树
后序遍历特性：
- 先处理子节点再处理自身
- 自然获取子树深度信息
层次遍历优势：
- 每层明确对应深度级别
- 队列长度 = 当前层节点数
空间效率权衡：
- BFS空间取决于最大宽度
- DFS空间取决于树高度

复杂度分析#

方法	时间复杂度	空间复杂度	适用场景
递归DFS	O(n)	O(h) [树高, 最坏O(n)]	代码简洁，树平衡时优
迭代BFS	O(n)	O(w) [最大宽度]	需要层次信息时
迭代DFS	O(n)	O(h) [树高]	深度优先需求时

代码实现#

递归法

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number}
12
 */
13
const maxDepth = (root) => {
14
    if (!root) return 0;
15
    const left = maxDepth(root.left);
16
    const right = maxDepth(root.right);
17
    return Math.max(left, right) + 1;
18
};

迭代法 BFS

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number}
12
 */
13
var maxDepth = function (root) {
14
    if (!root) return 0;
15
    let ans = 0;
16
    const queue = [root];
17

18
    while (queue.length) {
19
        let size = queue.length;
20
        while (size) {
21
            const node = queue.pop();
22
            if (node.left) queue.unshift(node.left);
23
            if (node.right) queue.unshift(node.right);
24
            size--;
25
        }
26
        ans++;
27
    }
28

29
    return ans;
30
};

迭代 DFS

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number}
12
 */
13
const maxDepth = (root) => {
14
    if (!root) return 0;
15
    const stack = [[root, 1]];  // [节点, 当前深度]
16
    let max = 0;
17

18
    while (stack.length) {
19
        const [node, depth] = stack.pop();
20
        max = Math.max(max, depth);  // 更新最大深度
21

22
        // 子节点入栈（深度+1）
23
        if (node.right) stack.push([node.right, depth + 1]);
24
        if (node.left) stack.push([node.left, depth + 1]);
25
    }
26
    return max;
27
};