[104] 二叉树的最大深度

深度优先搜索（DFS）

details

使用递归进行深度优先搜索，计算每个子树的深度，然后取最大值。

JavaScript 实现：

function maxDepth(root) {
    if (root === null) {
        return 0;
    }

    // 递归计算左子树和右子树的深度
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);

    // 返回左右子树深度的最大值加1（当前节点）
    return Math.max(leftDepth, rightDepth) + 1;
}

广度优先搜索（BFS）

details

使用队列进行广度优先搜索，逐层遍历二叉树，记录层数。

JavaScript 实现：

function maxDepth(root) {
    if (root === null) {
        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);
            }
        }

        // 完成一层的遍历，深度加1
        depth++;
    }

    return depth;
}