Как получить список всех предков в общем дереве Java

Question

У меня есть класс TreeNode, который представляет узел в дереве и класс LinkedTree. В этом я хочу получить список с каждым предком узла. В каждом узле я сохраняю значение, узел родителя и список со всеми дочерними элементами. Поэтому я должен иметь возможность получить список предков с родителем в узле, родителем этого узла и т. Д.

Я попробовал это рекурсивно. Вот две версии моего кода:

Версия 1:

public List<Position<E>> ancestors(Position<E> p) throws 
InvalidPositionException {  
    if(invalidPosition(p)) {
        throw new InvalidPositionException("Position is not in the current 
        tree");
    }
    List<Position<E>> ancestors = new ArrayList<>();
    if(!isRoot(p)) {
        ancestors.add(((TreeNode<E>) p).getParent());
        ancestors(((TreeNode<E>) p).getParent());
    }
    return ancestors;
}

Версия 2:

public List<Position<E>> ancestors(Position<E> p) throws 
InvalidPositionException {
     List<Position<E>> ancestors = new ArrayList<>();
     if(isRoot(p)) {
        return ancestors;
    }

    for(Position<E> e : positions()) {
        ancestors.add(((TreeNode<E>) e).getParent());
        if(e.equals(p)) {
            ancestors(((TreeNode<E>) e).getParent());
        }
    }
    return ancestors;
}

Answer 1

Возвращаемое значение метода ancestors () игнорируется; Вы должны использовать их.

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

Answer 2

Для вашей версии 1 вам необходимо либо передать список ancestors вместе с рекурсивным вызовом, либо добавить возвращенный список из рекурсивного вызова в текущий.

if(!isRoot(p)) {
    ancestors.add(((TreeNode<E>) p).getParent());

   //requires signature change and does not require a 'return' at the end of the method
    ancestors(((TreeNode<E>) p).getParent(), ancestors); 
}

Или

 if(!isRoot(p)) {
    ancestors.add(((TreeNode<E>) p).getParent());
   //Add the result of the recursive call to the current list
    ancestors.add(ancestors(((TreeNode<E>) p).getParent(), ancestors)); 
}
return ancestors;

Трудно комментировать вашу вторую версию, не видя реализации positions()