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

Question

Я делаю некоторую ревизию экзамена и нашел этот вопрос в прошлом экзаменационном листе:

Во-первых, будет ли кто-нибудь когда-нибудь реализовывать такое дерево или это просто проблема экзамена?

Во-вторых, я действительно не понимаю, как это сделать.Я хотел использовать BFS или DFS, но они работают только для двоичных деревьев, и я не очень хорошо разбираюсь в рекурсии, поэтому я тоже боролся с этим.не работает для общего случая, только это конкретное дерево:

public ArrayList<Integer> getLeafValues() {
    ArrayList<Integer> leafList = new ArrayList<>();
    Tree current = this;
    for (Tree t : current.children) {
        if (t.children.isEmpty()) {
            leafList.add(t.data);
        } else {
            for (Tree t2 : t.children) {
                if (t2.children.isEmpty()) {
                    leafList.add(t2.data);
                } else {
                    for (Tree t3 : t2.children) {
                        if (t3.children.isEmpty()) {
                            leafList.add(t3.data);
                        }
                    }
                }
            }
        }
    }
    return leafList;
}  

Любая помощь по этому вопросу будет отличной, как я уже сказал до пересмотра экзамена, а не домашней работой.Спасибо

Answer 1

Такие проблемы можно решить с помощью рекурсии:

public ArrayList<Integer> getLeafValues() {
    ArrayList<Integer> leafList = new ArrayList<>();
    getLeaves (this, leafList);
    return leafList;
}

public void getLeaves (Tree current, List<Integer> leafList)
{
    if (current.children.isEmpty()) {
        leafList.add(current.data);
    } else {
        for (Tree t : current.children) {
            getLeaves (t, leafList);
        }
    }
}

Рекурсия заканчивается, когда вы достигнете листа (т.е. дерева без дочерних элементов), и в этом случае вы добавляете этот лист к List.

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