Сложность: medium
Если задан корень бинарного дерева, верните все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов.
Пример:
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
👨💻 Алгоритм:
1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.
2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.
3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.
😎 Решение:
from collections import defaultdict
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findDuplicateSubtrees(root):
def serialize(node):
if not node:
return "#"
serial = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
count[serial] += 1
if count[serial] == 2:
result.append(node)
return serial
count = defaultdict(int)
result = []
serialize(root)
return result
Ставь 👍 и забирай 📚 Базу знаний