Day12-二叉树的最大深度

🔗 LeetCode 104 - Maximum Depth of Binary Tree

📌 题目描述

给定一个二叉树，找出其最大深度。

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

示例：

1
2
3

输入：[3,9,20,null,null,15,7]
输出：3
解释：最大路径是 3 -> 20 -> 7

💡 解题思路

我们可以使用递归或 BFS 层序遍历来解决：

递归法：最大深度 = 1 + max(左子树深度, 右子树深度)
层序遍历：每遍历一层，深度加一
时间复杂度：O(n)
空间复杂度：O(h)，h 为树的高度（递归栈）

✅ JavaScript 实现（递归）

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

✅ JavaScript 实现（BFS）

var maxDepth = function(root) {
    if (!root) return 0;
    let queue = [root];
    let depth = 0;

    while (queue.length > 0) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        depth++;
    }

    return depth;
};

🧠 思考拓展

如果要求“最小深度”呢？（LeetCode 111）
如何找出最长路径上的具体节点？
可否使用 DFS 的非递归写法？