BST层序遍历list.clear() and list = new ArrayList

Question

Context：我在 Java 中创建了一个 BinarySearchTree class 作为学习练习，因为我是 Java 的新手。我目前正在编写一个级别顺序遍历 (BFS) 的方法，该方法 returns 是每个级别的节点值列表列表，其中顶级列表索引代表级别编号，低级别列表每个索引包含该级别的节点值，例如对于这棵树

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

levelOrder() 方法会 return

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

问题：在实现中，我声明了一个名为'listOfLevels'的顶级列表来保存级别列表和一个名为[=38的低级列表=] 存储每个级别的节点（我打算跨级别清除和重用）。但是，我注意到，如果我在将 'level' 添加到 'listOfLevels' 之后调用 List.clear() 方法，我会在 'listOfLevels' 中为该方法的 [=48] 获取空列表=]值，像这样

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

我不确定为什么会这样。根据 ArrayList 文档，"As elements are added to an ArrayList, its capacity grows automatically," 所以我认为在使用 clear() 方法清除上一级的值后，从下一级添加节点值会显示在列表中。但这似乎没有用。我通过每次都为 'level' 显式分配一个新的 ArrayList 来修复它。

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

这是二叉搜索树中的相关位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; 
            ...
    }
}

这里是 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;
}

Answer 1

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

因为当您调用 clear 而不是创建新的数组列表时，您从未使用 new ArrayList() 分配新的 level 列表，所以您实际上是在一遍又一遍地使用同一个列表。

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

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

Answer 2

当您将 ArrayList 保存到 ArrayList 列表时，您并没有制作副本，因此它保存了相同的变量。这是因为 ArrayList 是指向内存中某个位置的指针；这才是真正被拯救的。通过清除 ArrayList，它会清除内存，这也会影响列表的 ArrayList 中保存的内存位置。使用新行而不是明文。

BST层序遍历list.clear() and list = new ArrayList

BST Level Order Traversal list.clear() and list = new ArrayList

java

memory-management

arraylist

tree-traversal

binary-search-tree