BST Level Order Traversal list.clear（）和list = new ArrayList

Context: I created a BinarySearchTree class in Java as a learning exercise since I'm new to Java. I'm currently writing a method for a level-order traversal (BFS) that returns a list of lists of node values for each level, where the top-level list index represents the level number and the lower-level list at each index contains the node values for that level, e.g. for this tree

上下文：我在Java中创建了一个BinarySearchTree类作为学习练习，因为我是Java的新手。我正在编写一个水平顺序遍历（BFS）的方法，它返回每个级别的节点值列表列表，其中*列表索引表示级别编号，每个索引包含的下级列表包含该级别的节点值，例如对于这棵树

       F
      / \
     /   \
    /     \
   B       G
  / \       \
 /   \       \
A     D       I
     / \     /
    C   E   H

The levelOrder() method would return

levelOrder（）方法将返回

[[F], [B, G], [A, D, I], [C, E, H]]

Problem: In the implementation, I declare a top-level list called 'listOfLevels' to hold the lists of levels and a lower-level list called 'level' to store the nodes at each level (which I intended to clear and reuse across levels). However, I noticed that if I called the List.clear() method on 'level' after adding it to 'listOfLevels', I would get empty lists inside 'listOfLevels' for the method's return value, like this

问题：在实现中，我声明了一个名为'listOfLevels'的*列表来保存级别列表和一个名为'level'的低级列表来存储每个级别的节点（我打算清除它并在各级别之间重用））。但是，我注意到如果在将'listOfLevels'添加到'listOfLevels'之后调用'level'上的List.clear（）方法，我会在'listOfLevels'中找到方法返回值的空列表，就像这样

[[], [], [], []]

I'm not sure why this happens. According to the ArrayList documentation, "As elements are added to an ArrayList, its capacity grows automatically," so I figured adding node values from the next level would show up in the list after clearing the previous level's values using the clear() method. This didn't seem to work, though. I fixed it by explicitly allocating a new ArrayList for 'level' each time instead.

我不确定为什么会这样。根据ArrayList文档，“As元素被添加到ArrayList，它的容量会自动增长”，所以我认为在使用clear（）方法清除上一级别的值后，添加下一级别的节点值会显示在列表中。但这似乎不起作用。我通过每次为'level'显式分配一个新的ArrayList来修复它。

Main Question: If an ArrayList grows automatically as elements are added, why do I need to allocate a new ArrayList each time? Why does calling clear() between levels result in empty lists for the top-level list?

主要问题：如果ArrayList在添加元素时自动增长，为什么每次都需要分配一个新的ArrayList？为什么在级别之间调用clear（）会导致*列表的空列表？

Here are the relevant bits from the Binary Search Tree class:

以下是二进制搜索树类的相关位：

public BinarySearchTree<K extends Comparable<K>, V> {
    private Node<K,V> root;
        ...
    public List<List<V>> levelOrder() {
        // see implementation below
    }
        ...
    private static class Node<K extends Comparable<K>, V> {
        private K key;
        private V value;
        private Node<K,V> left;
        private Node<K,V> right; 
            ...
    }
}

And here is the levelOrder() method implementation

这是levelOrder（）方法实现

public List<List<V>> levelOrder() {
    Queue<Node<K,V>> queue = new LinkedList<Node<K,V>>();
    List<List<V>> listOfLevels = new ArrayList<List<V>>();
    List<V> level = new ArrayList<V>();
    int currLevelCount = 1, nextLevelCount = 0;
    queue.add(root);

    while (!queue.isEmpty()) {
        Node<K,V> node = queue.remove();
        currLevelCount--;
        level.add(node.value);
        if (node.hasLeft()) {
            queue.add(node.left);
            nextLevelCount++;
        }
        if (node.hasRight()) {
            queue.add(node.right);
            nextLevelCount++;
        }
        if (currLevelCount == 0) {
            listOfLevels.add(level);
            //level.clear();    <-- why doesn't this work?
            level = new ArrayList<V>();
            currLevelCount = nextLevelCount;
            nextLevelCount = 0;
        }
    }
    return listOfLevels;
}

2 个解决方案

#1

If you call clear on the level list, you are clearing the list that you have just added to the listOfLevels, and then you start to re-use it.

如果在级别列表上调用clear，则表示您正在清除刚刚添加到listOfLevels的列表，然后开始重新使用它。

Since you never allocate a new level list with new ArrayList() when you call clear instead of creating a new arraylist, you are effectively using the same list over and over again.

由于在调用clear而不是创建新的arraylist时从未使用新的ArrayList（）分配新的级别列表，因此您实际上一遍又一遍地使用相同的列表。

And since you are clearing it every time, you will never have an values in the lists under listOfLevels.

而且由于您每次都清除它，因此listOfLevels下的列表中永远不会有值。

Calling new ArrayList instead of clear is indeed the correct solution.

调用新的ArrayList而不是clear是确实正确的解决方案。

#2

When you save your ArrayList to your List of ArrayLists you are not making a copy so it is saving the same variable. This is because an ArrayList is a pointer to a spot in memory; this is what is actually being saved. By clearing the ArrayList it clears the memory which also affects the saved memory location in your ArrayList of Lists. Use your new line instead of the clear.

将ArrayList保存到ArrayLists列表时，您没有复制，因此它保存了相同的变量。这是因为ArrayList是指向内存中某个点的指针;这就是实际保存的内容。通过清除ArrayList，它会清除内存，这也会影响列表的ArrayList中保存的内存位置。使用新行而不是清除行。

#1