二叉树的最大深度

题目描述

给定二叉树根节点 root，返回其最大深度。

最大深度：从根节点到最远叶子节点的最长路径上的节点数。

示例

示例 1：

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

    3
   / \
  9  20
     / \
    15  7

输出: 3

示例 2：

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

示例 3：

输入: root = []
输出: 0

示例 4：

输入: root = [0]
输出: 1

解题思路

DFS 递归：当前树的最大深度等于左子树和右子树最大深度的较大值再加 1（根节点自身）。递归终止条件是空节点返回 0。

BFS 迭代：层序遍历，每遍历完一层深度加 1，遍历完所有层后得到的深度即为最大深度。

代码实现

/**
 * 方法一：DFS 递归版
 * @param {TreeNode} root - 二叉树根节点
 * @returns {number} 最大深度
 */
function maxDepthDFS(root) {
    if (!root) return 0;
    return Math.max(maxDepthDFS(root.left), maxDepthDFS(root.right)) + 1;
}

/**
 * 方法二：BFS 迭代版（层序遍历）
 * @param {TreeNode} root - 二叉树根节点
 * @returns {number} 最大深度
 */
function maxDepthBFS(root) {
    if (!root) return 0;
    let depth = 0;
    const queue = [root];
    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;
}

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：DFS 为 O(h)（递归栈深度），h 为树高；BFS 为 O(w)（队列宽度），w 为树的最大宽度。最坏情况均为 O(n)。

root = [3,9,20,null,null,15,7]

3