Учитывая бинарное дерево, вернуть все повторяющиеся поддеревья. Для каждого типа повторяющихся поддеревьев вам нужно только вернуть корневой узел любого одного из них.
Два дерева дублируются, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Эта проблема была мотивацией для Merkle Trees. Я решил эту проблему, разработав структуру, которая поддерживает структуру поддеревьев с точки зрения триплета root.val, количества элементов в левом дочернем элементе, количества элементов в правом дочернем элементе. Ведя словарь всех таких троек, я искал равенство среди элементов, принадлежащих одному и тому же ключу в словаре.
Предложенный подход к решению подсказал мне Merkle Trees. Дерево Меркла — это структура данных на основе хэшей, которая является обобщением списка хэшей. Это древовидная структура, в которой каждый лист-узел представляет собой хеш блока данных, а каждый нелистовой узел — это хэш его дочерних элементов. Как правило, деревья Меркла имеют коэффициент ветвления, равный 2, что означает, что каждый узел имеет до 2 дочерних элементов. Деревья Меркла имеют очень небольшие накладные расходы по сравнению со списками хэшей. Бинарные деревья Меркла работают аналогично бинарным деревьям поиска в том смысле, что их глубина ограничена их коэффициентом ветвления, равным 2.
