二叉树最小深度：BFS与DFS的JavaScript实现与比较

二叉树的最小深度是指从根节点到最近的叶子节点的最短路径上的节点数量。叶子节点是指没有子节点的节点。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决这个问题。BFS通常更适合用于寻找最短路径的问题，因为它会逐层遍历节点，一旦找到叶子节点就可以立即返回结果。

使用BFS的JavaScript实现

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function minDepth(root) {
    if (!root) return 0;

    const queue = [[root, 1]]; // 使用队列存储节点及其深度

    while (queue.length > 0) {
        const [node, depth] = queue.shift();

        // 如果当前节点是叶子节点，返回当前深度
        if (!node.left && !node.right) {
            return depth;
        }

        // 将子节点加入队列
        if (node.left) {
            queue.push([node.left, depth + 1]);
        }
        if (node.right) {
            queue.push([node.right, depth + 1]);
        }
    }
}

// 示例用法
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

console.log(minDepth(root)); // 输出: 2

解释

1. 队列初始化：我们使用一个队列来存储节点及其深度。初始时，队列中只有根节点，深度为1。
2. BFS遍历：我们从队列中取出节点，检查它是否是叶子节点。如果是，返回当前深度。如果不是，将其子节点加入队列，并增加深度。
3. 终止条件：当队列为空时，遍历结束。

复杂度分析

• 时间复杂度：O(N)，其中N是二叉树中的节点数量。在最坏情况下，我们需要访问所有节点。
• 空间复杂度：O(N)，在最坏情况下，队列中需要存储所有节点。

使用DFS的JavaScript实现

虽然BFS更适合这个问题，但DFS也可以实现：

function minDepth(root) {
    if (!root) return 0;

    if (!root.left) {
        return minDepth(root.right) + 1;
    }
    if (!root.right) {
        return minDepth(root.left) + 1;
    }

    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

解释

1. 递归终止条件：如果当前节点为空，返回0。
2. 单子树情况：如果左子树或右子树为空，递归计算另一棵子树的深度。
3. 双子树情况：如果左右子树都存在，递归计算左右子树的最小深度，并取较小值加1。

复杂度分析

• 时间复杂度：O(N)，其中N是二叉树中的节点数量。在最坏情况下，我们需要访问所有节点。
• 空间复杂度：O(H)，其中H是二叉树的高度。在最坏情况下，递归栈的深度等于树的高度。

总结

• BFS：适合寻找最短路径，空间复杂度较高。
• DFS：代码简洁，但在某些情况下（如树不平衡）可能会导致较高的递归深度。

根据具体场景选择合适的算法。