Объект не удаляется из ArrayList

Question

Существует общая древовидная структура данных. Теперь это класс узла будет выглядеть примерно так.

private static class Node {
    int data;
    ArrayList<Node> children = new ArrayList<>();
  }

Формирование DS строится исключительно на основе ввода данных. Теперь мне нужно удалить все листовые узлы. Приведенный ниже код не может удалить дочерние элементы, которые уже присутствуют в его экземпляре-члене.

public static void removeLeaves(Node node) {
ArrayList<Node> nodeChildrenList = node.children;
int childrenSize = nodeChildrenList.size();
for(int i = 0; i < childrenSize; i++){
    Node child = nodeChildrenList.get(i);
    removeLeaves(child);
    if(child.children.size() == 0){
        child.children.remove(child); // Problem
    }
}
}

Я не могу понять, что дочерний объект (узел) не удаляется из ArrayList. Но Iterator работает нормально. Я даже пробовал отлаживать на каждом этапе. Когда точка останова достигает child.children.remove(child); линия. Это не завершает.

Пока этот код работает как шарм.

    ArrayList<Node> nodeChildrenList = node.children;
    // int childrenSize = nodeChildrenList.size();
    Iterator itr = nodeChildrenList.iterator();
    while(itr.hasNext()){
       Node child = (Node)itr.next();
       if(child.children.size() == 0){
           itr.remove();
       }
       removeLeaves(child);
    }
    // for(int i = 0; i < childrenSize; i++){
    //     Node child = nodeChildrenList.get(i);
    //     removeLeaves(child);
    //     if(child.children.size() == 0){
    //         child.children.remove(child);
    //     }
    // }
  }

Answer 1

Давайте посмотрим, что делает ваш removeLeaves с циклом for. Добавлены комментарии ниже

ArrayList<Node> nodeChildrenList = node.children;
int childrenSize = nodeChildrenList.size();
for(int i = 0; i < childrenSize; i++){    // Loop through each of node's children
    Node child = nodeChildrenList.get(i); // Get the child of node at index i
    removeLeaves(child);                  // recursively call removeLeaves with the child
    if(child.children.size() == 0){       // If the node's child has no children
        // This is a problem because you are telling the program to remove the node's 
        // child from the node's child's children, not from the node's children.
        child.children.remove(child);     
    }
}

Надеюсь, это имеет смысл, вы звоните removeв неправильном списке. Чтобы делать то, что вы хотите, вы хотите позвонитьnode.children.remove(child) так как вы хотите удалить дочерний узел из списка дочерних узлов.

Однако это также вызывает проблемы, потому что теперь вы изменили структуру, через которую проходите. Например, давайте рассмотрим очень простой случай.

         1
        / \
       2   3

В этом случае у нас есть корневой узел со значением 1 и два дочерних узла. Первый дочерний элемент имеет значение 2 и не имеет дочерних элементов. Второй дочерний элемент имеет значение 3 и не имеет дочерних элементов.

Итак, если мы пройдем через removeLeaves построчно, посмотрим, что получится.

при вызове с корневым узлом:

ArrayList<Node> nodeChildrenList = node.children; // nodeChildrenList contains two nodes - the ones with values 2 and 3

int childrenSize = nodeChildrenList.size(); // childrenSize is 2
for(int i = 0; i < childrenSize; i++){  // Start with i = 0
    Node child = nodeChildrenList.get(i); // The first child is the one with value 2
    removeLeaves(child);  // Call remove leaves again with the child with value 2

Мы вернемся к этой итерации метода позже, теперь мы снова погрузимся в первый дочерний элемент.

ArrayList<Node> nodeChildrenList = node.children; // The first node has no children, so this is an empty list
int childrenSize = nodeChildrenList.size(); // size is 0
for(int i = 0; i < childrenSize; i++){  // None of this gets called
    Node child = nodeChildrenList.get(i);
    removeLeaves(child);
    if(child.children.size() == 0){
        node.children.remove(child); 
    }
}

теперь, когда мы вышли из первого дочернего элемента (со значением 2), мы заканчиваем итерацию цикла с корневым узлом

    if(child.children.size() == 0){ // child is still the first child (value 2), and it doesn't have any children, so this is true
        node.children.remove(child); // So we remove it from the root node's children. 
    }
}

Теперь у нас есть корневой узел с одним дочерним узлом (со значением 3). Отлично, правда? Ну не очень. Поскольку мы изменили структуру, через которую проходит цикл, мы столкнемся с проблемой. Давайте пройдемся по следующей итерации цикла с дочерними элементами корневого узла.

for(int i = 0; i < childrenSize; i++){  // i = 1 and childrenSize of the root node is 2, so we can continue
    Node child = nodeChildrenList.get(i); // Uh oh, we don't have a child at index 1!

Проблема здесь в том, что, поскольку в nodeChildrenList произошли структурные изменения, теперь в списке есть только один элемент (с индексом 0) - элемент со значением 3. Нет элемента с индексом 1, поэтому это вызывает исключение IndexOutOfBoundsException. Вот почему вы хотите использовать итератор при внесении структурных изменений в коллекцию, которую вы просматриваете.