计算二叉树最大深度：递归与迭代方法详解

计算二叉树的最大深度是一个常见的算法问题，通常可以通过递归或迭代的方式来解决。下面我将分别介绍这两种方法，并提供相应的代码实现。

1. 递归方法

递归方法是最直观的解决方案。对于每个节点，我们递归地计算其左子树和右子树的深度，然后取两者中的较大值，并加1（当前节点的深度）。

function maxDepth(root) {
    if (root === null) {
        return 0;
    }
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

2. 迭代方法（广度优先搜索）

迭代方法通常使用广度优先搜索（BFS）来实现。我们可以使用队列来存储每一层的节点，并在遍历每一层时增加深度计数。

function maxDepth(root) {
    if (root === null) {
        return 0;
    }
    const queue = [root];
    let depth = 0;
    while (queue.length > 0) {
        const levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const currentNode = queue.shift();
            if (currentNode.left !== null) {
                queue.push(currentNode.left);
            }
            if (currentNode.right !== null) {
                queue.push(currentNode.right);
            }
        }
        depth++;
    }
    return depth;
}

3. 复杂度分析

• 时间复杂度：无论是递归还是迭代方法，时间复杂度都是 O(N)，其中 N 是二叉树中节点的数量。每个节点都会被访问一次。
• 空间复杂度：
  • 递归方法的空间复杂度取决于递归栈的深度，最坏情况下（树完全不平衡）为 O(N)，最好情况下（树完全平衡）为 O(logN)。
  • 迭代方法的空间复杂度取决于队列的大小，最坏情况下为 O(N)。

4. 使用场景

• 递归方法：代码简洁，易于理解，适合树结构较为平衡的情况。
• 迭代方法：适合树结构较为不平衡的情况，避免递归栈溢出的风险。

5. 总结

计算二叉树的最大深度是一个基础但重要的算法问题，理解递归和迭代两种方法有助于你在不同的场景下选择最合适的解决方案。在实际开发中，递归方法通常更为常用，但在处理深度较大的树时，迭代方法可能更为安全。

希望这些信息对你有所帮助！如果你有更多问题或需要进一步的解释，请随时提问。