java - 使用 ArrayList 和递归避免 java.util.ConcurrentModificationException

Question

我正在尝试从给定的边和根构造二叉树。我迭代所有行并将左子节点设置为给定节点(如果找到给定节点的第二次出现，则设置右子节点)。当设置子节点时，我从 ArrayList 中删除该元素并在子节点上递归调用函数。

List<Integer[]> edges = new ArrayList<>();

这个数组列表例如:

3 4
3 0
4 5
1 3
2 4 

根目录是1。我有类节点

public class Node {
public Node left;
public Node right;
public int key;

public Node(int k) {
    key = k;
    left = null;
    right = null;
}
...}

我构建树的函数是:

public static void edgeToNodes(Node root) {
    if (root == null) return;
    int count = 0;

    for (Iterator<Integer[]> iterator = edges.iterator(); iterator.hasNext(); ) {
        Integer[] edge = iterator.next();
        for (int i = 0; i < edge.length; i++) {
            if (edge[i] == root.key) {
                if (count == 0) {
                    Node left;
                    if (i == 0) {
                        left = new Node(edge[1]);
                        root.setLeft(left);
                    } else {
                        left = new Node(edge[0]);
                        root.setLeft(left);
                    }

                    iterator.remove();
                    count++;
                    edgeToNodes(left);
                } else {
                    Node right;
                    if (i == 0) {
                        right = new Node(edge[1]);
                        root.setRight(right);
                    } else {
                        right = new Node(edge[0]);
                        root.setRight(right);
                    }

                    iterator.remove();
                    edgeToNodes(right);
                }
            }
        }
    }
}

问题是它在 Integer[] edge = iterator.next(); 和 edgeToNodes(left); 行上给了我 java.util.ConcurrentModificationException 。 如何避免此异常？

Answer 1

您在迭代列表时从列表中删除元素。

如果您仅通过一个迭代器来完成它，它就会起作用。问题是您使用递归，因此创建了多个修改同一列表的迭代器。这会导致 ConcurrentModificationException。

您可以以更加迭代的方式构建节点。

• 从根节点开始。
• 维护要访问的节点列表(我们称之为 pendingNodes)。
• 使用根节点对其进行初始化。
• 虽然待处理节点列表不为空:
  • 获取 pendingNodes 的第一个元素。
  • 找到其潜在的子项。
  • 如果有一些子节点尚未访问过
    • 将它们链接到父节点。
    • 将它们添加到pendingNodes列表中。

这是代码示例:

public class Problem {

  private List<Integer[]> edges;
  private LinkedList<Node> pendingNodes = new LinkedList<>();
  private Map<Integer, Node> nodeMap = new HashMap<>();
  private Set<Integer> visitedNodes = new HashSet<>();

  public Problem(List<Integer[]> edges) {
    this.edges = edges;
  }

  public void run(Integer root) {
    //Initialization
    Node rootNode = new Node(root);
    this.pendingNodes.add(rootNode);
    this.nodeMap.put(root, rootNode);

    while(!pendingNodes.isEmpty()) {
      Node parent = pendingNodes.poll();
      for (Integer[] edge : edges) {
        if(edge[0].equals(parent.getKey())) {
          link(parent, edge[1]);
        } else if (edge[1].equals(parent.getKey())) {
          link(parent, edge[0]);
        }
      }
      visitedNodes.add(parent.getKey());
    }
  }

  public void link(Node parent, Integer child) {
    if(!visitedNodes.contains(child)) {
      //get the corresponding node, create it if not exists
      Node childNode = nodeMap.get(child);
      if (childNode == null) {
        childNode = new Node(child);
        nodeMap.put(child, childNode);
        pendingNodes.add(childNode);
      }

      //Choose between left and right...
      if (parent.getLeft() == null) {
        parent.setLeft(childNode);
      } else {
        parent.setRight(childNode);
      }
    }
  }

  public static void main(String[] args) {

    //Build the input dataset
    List<Integer[]> edges = Arrays.asList(
        new Integer[]{3, 4},
        new Integer[]{3, 0},
        new Integer[]{4, 5},
        new Integer[]{1, 3},
        new Integer[]{2, 4}
    );

    Problem problem = new Problem(edges);
    problem.run(1);

    Map<Integer, Node> nodeMap = problem.nodeMap;
    for (Node node : nodeMap.values()) {
      System.out.println(node);
    }
  }

}

输出(我自定义了Node#toString()):

0 => {null, null}
1 => {3, null}
2 => {null, null}
3 => {4, 0}
4 => {5, 2}
5 => {null, null}