java - 为什么这个 MinDepth 级别的解决方案与递归解决方案相比如此慢？

Question

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

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

将返回最小深度为 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)，但对于 Java 中的排队操作，使用 ArrayDeque 是一种更快且语义更合适的数据结构。

此外，通过在 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 结果，但同样，考虑到它们的微小程度，我不愿意跳出任何结论。测试用例似乎是。