Видел этот вопрос следующим образом и не имеет понятия, как ее решить:Как разделить дерево на максимические поддеревья с четными узлами?
Даны произвольное дерево, не разбить его на стольких поддерева, как вы можете и числа узлов поддерева должно быть четным.
Есть идеи?
Возможно, что-то подобное, пройдя через дерево, получить счет для каждого узла. Добавьте узел, если счетчик четный.
List<Node> subTrees = new List<Node>();
int GetCount(Node root)
{
if (root == null) return 0;
return GetCount(root.Left) + GetCount(root.Right) + 1;
}
void BuildSubTrees(Node root)
{
if (root == null) return;
if(GetCount(root) % 2 == 0){subTrees.Add(root);}
BuildSubTrees(root.Left);
BuildSubTrees(root.Right);
}
Я предположил, что это двоичное дерево. Если это не так, то вместо left или right пройдите все это neighbors.
Это решение предполагает, что разные поддеревья могут совместно использовать узлы друг с другом. В исходном вопросе эти свойства не упоминаются. Поэтому нам, возможно, придется решать оба случая. 1> поддерево не может обмениваться узлами. 2> поддерево может обмениваться узлами. – q0987
Правда, в этом случае перед добавлением узла в список вам нужно убедиться, что Узел не имеет ни самого себя, ни каких-либо детей в любом из узлов и их дочерних элементов в списке. В основном другой метод утилиты для перемещения по дереву. –
Я бы разорвать эту проблему следующим образом:
Просьба пояснить: должны ли все поддеревья иметь четное число узлов или у нас должно быть максимальное количество поддеревьев с четным числом узлов. –
Основываясь на моем понимании, вопрос заключается в том, чтобы найти как можно больше поддерева, разложив оригинальное дерево с ограничением на то, что поддерево должно иметь четное количество узлов. – q0987
Итак, если у дерева есть нечетное число узлов, решения не будет? –