1

我正在做一些简单的算法问题并玩弄 ArrayDeque。

比如这个：

https://leetcode.com/problems/maximum-depth-of-binary-tree/submissions/

使用 BFS 时，我注意到 offerLast 和 pollFirst / offerFirst 和 pollLast 都给出了相同（正确）的答案。

何时使用哪个有最佳实践吗？由于这应该是一个队列，我认为我们应该提供最后并使用 pollFirst。但是为什么 offerFirst / pollLast 也有效？

 public int maxDepth(TreeNode root) {
        // do BFS
        if (root == null) return 0;
        
        int depth = 0;
        ArrayDeque<TreeNode> queue = new ArrayDeque();
        queue.offerLast(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                TreeNode curr = queue.pollFirst();
                if (curr.left != null) queue.offerLast(curr.left);
                if (curr.right != null) queue.offerLast(curr.right);
            }
            depth++;
        }
        
        return depth;
    }

另外，我知道我们不需要队列为 ArrayDeque 类型。只需一个简单的队列即可工作，而队列仅提供默认为 FIFO 实现的报价/轮询（offerLast，pollFirst）

4

1 回答 1

1

但是为什么 offerFirst / pollLast 也有效？

因为队列的“开始”和“结束”实际上只是任意决定的。

您可以将第一个元素称为“开始”，将最后一个元素称为“结束”。在这种情况下，入队offerLast和pollFirst出队。

由于数组双端队列是线性数据结构，因此您可以“翻转”并说，我将第一个元素称为队列的“结束”，将最后一个元素称为队列的“开始”。如果您这样想，那么您将通过调用offerFirst入队并通过出队pollLast。

解释这一点的另一种方法是表明这些只是两个观点：

假设我们站在双端队列的两端。我们都认为离我们最近的元素是双端队列的“第一个元素”。

   the deque;
  a b c d e f g h
^                 ^
|                 |
you               me

你在 . 旁边放了一个新元素a。从你的角度来看，这是offerFirst. 从我的角度来看，你会做的offerLast！

现在假设您删除了h. 从你的角度来看，这是pollLast. 从我的角度来看，这看起来像pollFirst- 你正在删除你的“最后一个元素”，但它是我的“第一个元素”。

但是，请注意，官方决定第一个元素是队列的开头，最后一个元素是结尾——这就是接口ArrayDeque的实现Queue方式——所以如果你从 调用方法Queue，比如offer，它将调用offerLast。

尽管如果您有自己的开始和结束概念，它仍然有效，但遵循“开始”和“结束”的官方定义仍然是一个好习惯（实际上只使用offerand poll！）。如果您使用pollLastand offerFirst，如果您将双端队列传递给另一段需要Queue.

于 2021-05-17T04:01:23.753 回答