与递归解决方案相比，为什么这个 MinDepth 级解决方案这么慢？

Question

问题是找到二叉树的最小深度，使得运行在以下树上：

    *           :Level 1
   / \
  *   *         :Level 2
     / \
    *  NULL     :Level 3

mindepth return 会是 2 吗

根据 leetcode，我能够得到一个 100% 击败其他解决方案的递归解决方案，这对我来说没有意义，因为如果它必须访问每个节点的每个子节点（实现DFS）。

我改为决定以 BFS 方式而不是 DFS 方式进行，并检查每个级别中是否有一个节点没有子节点，这将是最小深度。

这是我的递归解决方案：

public int minDepth(TreeNode root) {
    if (root == null)
        return 0;
    else if (root.left == null) 
        return minDepth(root.right) + 1;
    else if (root.right == null) 
        return minDepth(root.left) + 1;
    else 
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

这是我的水平解决方案：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        ArrayList<TreeNode> q = new ArrayList<TreeNode>(); // We will store each new node here
        q.add(root); // add the root to our queue
        return root != null ? minDepthHelper(q, 0) : 0; // If the root node is null, dont bother and return 0

    }

    private int minDepthHelper(ArrayList<TreeNode> q, int depth){
        if(q.size() == 0) // Empty queue means nothing to do, so return
            return depth;

        int size = q.size(); // How many we will need to pop (the parents)
        for(int i = 0; i < size; i++){
            TreeNode curr = q.get(0); // FIFO!
            if(curr.left == null && curr.right == null){
                return depth +1; // If you have no children, then you are a leaf so return your depth. 
                                            // nodes 0 through size are on the same level, so any of them , if they have 
                                            // no children, will return the same value which will be min depth.
            }else{
                // Add only non-null children!
                if(curr.left != null)
                    q.add(curr.left);
                if(curr.right != null)
                    q.add(curr.right);
            }
            q.remove(0);
        }
        // Will only reach here if no nodes in level depth have no right and no left
        return minDepthHelper(q, depth+1);
    }
}

有人可以解释为什么第二种解决方案速度较慢，尽管它应该进行较少的比较吗？

Answer 1

我不会太看重 LeetCode 百分比。当我提交你的递归解决方案时，它显示它超过了 34%。 LeetCode 还显示了 100% 和 34% 段的完全相同的示例代码。人们只能猜测他们的测试用例到底是什么。我在 1 毫秒内提交了所有实现运行，所以很可能，他们的所有 41 个测试用例都是非常小的树，因此性能差异完全可以忽略不计。您也不知道哪种树结构在示例案例中占主导地位——它们可能或多或少都是最坏情况下的时间复杂度，在这种情况下，BFS 与 DFS 相比几乎没有优势。

考虑到这一点，让我们在大型测试用例上对您的代码进行基准测试，看看我们是否可以获得一些在 LeetCode 提供的黑盒测试环境中无法获得的理解。

在我们开始之前，让我们检查一下您的 BFS 解决方案，它使用递归并像处理队列一样操作 ArrayList。的确，ArrayList 移位操作的分摊时间为 O(1)，但使用 ArrayDeque 是一种更快且语义上更合适的数据结构，用于 Java.

中的排队操作

此外，通过在 BFS 实现中使用递归，您否定了 BFS 的主要优点之一，即它是迭代的。不必操纵调用堆栈应该会减少很多开销。

综合起来，我会像这样编写 BFS 函数：

public int minDepth(TreeNode root) {
    ArrayDeque<Pair<TreeNode, Integer>> q = new ArrayDeque<>();
    q.offer(new Pair(root, 1));

    while (!q.isEmpty()) {
        Pair<TreeNode, Integer> curr = q.poll();

        if (curr.first != null) {
            if (curr.first.left == null && curr.first.right == null) {
                return curr.second;
            }

            q.offer(new Pair(curr.first.left, curr.second + 1));
            q.offer(new Pair(curr.first.right, curr.second + 1));
        }
    }

    return 0;
}

现在，一个快速基准测试。这里，BFS2 是你的 BFS 实现，BFS 是我的：

long BFSTotal = 0;
long BFS2Total = 0;
long DFSTotal = 0;

for (int i = 0; i < 10000; i++) {
    TreeNode root = randomTree(10000);

    long start = System.currentTimeMillis();
    minDepthDFS(root);
    DFSTotal += System.currentTimeMillis() - start;

    start = System.currentTimeMillis();
    minDepthBFS(root);
    BFSTotal += System.currentTimeMillis() - start;

    start = System.currentTimeMillis();
    minDepthBFS2(root);
    BFS2Total += System.currentTimeMillis() - start;
}

System.out.println("BFS: " + BFSTotal);
System.out.println("BFS2: " + BFS2Total);
System.out.println("DFS: " + DFSTotal);

此代码创建 10000 棵不同的树，每棵树有 10000 个节点，使用抛硬币算法创建，并且运行在每棵树上设置算法。以下是一些运行的结果：

BFS: 1906
BFS2: 5484
DFS: 3351

BFS: 1709
BFS2: 6101
DFS: 3773

BFS: 1527
BFS2: 5567
DFS: 3856

继续 run the code yourself 并进行一些实验。我不认为这些结果是绝对决定性的，但它们确实强化了我的基本前提：BFS 胜过 DFS，因为开销更少，并且有可能提前退出（最坏情况下的时间复杂度相同），并且非递归 BFS 实现使用高效的数据结构击败了使用低效数据结构的递归 BFS 实现。

这也表明您的 BFS 实现大约是 DFS 实现的两倍，这可能解释了您的 LeetCode 结果，但同样，我会犹豫是否跳转到任何鉴于他们的测试用例看起来有多小，得出结论。

与递归解决方案相比，为什么这个 MinDepth 级解决方案这么慢？

Why is this MinDepth level solution so slow compared to recursive solution?

java

binary-tree

depth-first-search

breadth-first-search