在递归函数中使用一对列表时如何解决 ConcurrentModificationException?

Question

所以我试图通过递归设置每个节点的子节点来平衡二叉搜索树：

public void balanceTheTree(){
root = balance(keys, names);
}
public Node balance(List<Integer> keyList, List<String> nameList){
buildArrays(root);
if(root == null){
return null;
}
else{
int newRootIndex = keyList.size()/2;
Node focusNode = new Node(keyList.get(newRootIndex), nameList.get(newRootIndex));
focusNode.leftChild = balance(keyList.subList(0, newRootIndex), nameList.subList(0, newRootIndex));
focusNode.rightChild = balance(keyList.subList(newRootIndex+1, keyList.size()),nameList.subList(newRootIndex+1, nameList.size()));
return focusNode;
}
}

buildArrays() 使用按顺序遍历将树值(名称)和键(键)存储在各自的列表中。名称是List<String>，键是List<Integer>。

不幸的是，平衡会在任何尝试访问列表的行上抛出异常。

这是错误：

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(Unknown Source)
at java.util.ArrayList$SubList.size(Unknown Source)
at BinaryTree.balance(BinaryTree.java:43)
at BinaryTree.balance(BinaryTree.java:45)
at BinaryTree.balanceTheTree(BinaryTree.java:34)
at tester.main(tester.java:30)

其中第 43 行int newRootIndex = keyList.size()/2;

谢谢！

public void buildArrays(Node focusNode){
if(focusNode != null){
buildArrays(focusNode.leftChild);
names.add(focusNode.name);
keys.add(focusNode.Key);
buildArrays(focusNode.rightChild);
}
}

Answer 1

问题是您使用keyList.subList()，您正在向其添加新元素，这是ConcurrentModificationException的原因。

传递实际子列表的副本，而不是子列表，例如new ArrayList<>(keylist.subList(0, 4)).

Answer 2

选项 1：如果您使用的是 list.remove 函数，请使用 list iterator.renove() 选项 2：尝试以性能成本计算 CopyOnWriteArrayList 选项 3：将列表转换为数组并进行操作