Я должен разработать алгоритм под дополнительную домашнюю работу. Этот алгоритм должен сжимать двоичное дерево, преобразовывая его в DAG, удаляя повторяющиеся поддеревья и перенаправляя все эти соединения в одно левое исходное поддерево. Например, у меня есть дерево (я даю предварительный порядок узлов):

1 2 1 3 2 1 3

Алгоритм должен удалить правое соединение (правое поддерево, что означает 2 1 3) из 1 (корень) и перенаправить его на левое соединение (потому что эти поддеревья одинаковы и левый был первым в предзаказе, поэтому мы оставляем только левое)

То, как я это вижу: я передаю предзаказ дерева. Для текущего узла 'w' я запускаю рекурсию, которая должна обнаружить (если она существует) исходное поддерево, равное поддереву с корнем 'w'. Я обрезаю рекурсию, если я нахожу равное поддерево (и я делаю то, что должно быть сделано), или когда я получаю «w» в моем поиске той же рекурсии поддерева. Конечно, я предсказываю некоторые небольшие улучшения, такие как сравнение только поддеревьев с равным количеством узлов.

Если я не ошибаюсь, это дает сложность O (n ^ 2), где n - количество узлов данного двоичного дерева. Есть ли шанс сделать это быстрее (я думаю, что это так). Возможен ли линейный алгоритм?

Жаль, что мой алгоритм, наконец, имеет сложность O (n ^ 3). Ваши ответы с хешированием, вероятно, будут очень полезны для меня через некоторое время, когда я узнаю гораздо больше .. Пока это слишком сложно для меня ..

Последний вопрос. Есть ли шанс сделать это в O (n ^ 2), используя элементарные методы (не хэширование)?