Количество повторяющихся поддеревьев в N-арном дереве

Учитывая корень n-арного дерева , задача состоит в том, чтобы найти количество поддеревьев, которые имеют дубликаты в n-арном дереве. Два дерева дублируются, если они имеют одинаковую структуру с одинаковыми значениями узлов.

Примеры:

Input: 1 N 2 2 3 N 4 N 4 4 3 N N N N N
Output: 2
Explanation: [4], [3] are duplicate subtree.

Structure of the tree

Input: 1 N 2 3 N 4 5 6 N N N N
Output: 0
Explanation: No duplicate subtree found.

Structure of the tree

Подход: Эта проблема может быть решена с помощью упорядоченного обхода Дерева.

The idea is to store the inorder traversal of every vertex in the form of string and put this string in a map. 

So after inorder traversal of the complete tree we will have all distinct strings in map along with their frequencies. Now we can simply iterate over the map and check if frequency of the string is greater than 1, then more than 1 tree have same structure. So increment the answer.

Для реализации идеи выполните следующие шаги:

• Прежде всего, объявите неупорядоченную карту и сохраните в ней неупорядоченный обход дерева.
• Для каждой вершины сохраните неупорядоченный обход ее поддерева на карте.
• После этого просто проверьте частоту строк.
  • Если больше 1, то считать. В противном случае нет.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(V)
Вспомогательное пространство: O(V ² ), потому что мы сохраняем строку для каждой вершины, а максимальная длина строки может быть V

Статьи по Теме:

• Общие деревья (N-арные деревья)
• Неупорядоченный обход N-арного дерева