Задача для программистов! Не для садоводов!)))
Задача:
В структуре "обычное дерево" найти наибольшее количество ребёр которые можно удалить, чтобы получить лес четных деревьев.
Вернуть линейный список пар вершин для которых надо разорвать связь (удалить ребро), i-й элемент - это родительская вершина, i+1-й элемент - это её наследник.
Например есть дерево:
Результирующий список в данном примере: 1,2,2,7,3,8
Пояснения:
Обычное дерево - структура данных, в которой узлы (элементы) имеют произвольное количество дочерних узлов.
Ребра - связи между узлами.
Лес - множество деревьев.
Уровень сложности:
Собеседование в Гугл
Общий шаблон решения задачи:
Разделение дерева на чётные возможно только если количество узлов в дереве - чётное.
Например: 10 мы можем разбить ТОЛЬКО на четные числа - 2, 8. А вот 9 не получится.
Получается что нам необходимо проверять каждое поддерево нашего дерева на чётность и если поддерево чётное то добавлять родителя и текущий проверяемый узел в список.
Решение на Java:
// найти лес, состоящий из чётных деревьев
public ArrayList<T> EvenTrees() {
ArrayList<T> resultList = new ArrayList<>();
SimpleTreeNode<T> node = Root; // свой тип данных - простой узел
List<SimpleTreeNode<T>> listTemp = new ArrayList<>();
listTemp.add(node);
while (!listTemp.isEmpty()) {
node = listTemp.remove(0);
SimpleTree<T> tempTree = new SimpleTree<>(node); // создаем поддерево начиная с корня
// работаем только с четными деревьями
if (tempTree.Count() % 2 == 0) { // Count - метод подсчета количества узлов в дереве
if (node.Parent != null) { // если мы не на первом (корне) узле дерева
resultList.add(node.Parent.NodeValue);
resultList.add(node.NodeValue);
}
listTemp.addAll(node.Children);
}
}
return resultList;
}