---
round: 1
ticket_no: 29
source_no: 29
slug: find-duplicate-subtrees
topic: Tree
difficulty: Medium
leetcode_id: 652
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 29 — Find Duplicate Subtrees

## Условие (как предъявлено)

Дан корень бинарного дерева `root`. Нужно найти все дублирующиеся поддеревья. Для каждого повторяющегося поддерева вернуть корень одного из них. Два поддерева считаются дубликатами, если у них одинаковая структура и одинаковые значения в соответствующих узлах.

```
Input:  root = [1,2,3,4,null,2,4,null,null,4]  →  [[2,4],[4]]
```

Constraints: до 5000 узлов.

## Ответ

> Здесь нам нужно написать метод сериализации дерева: то есть мы обходим дерево, превращаем его в строку и записываем в хранилище вот этих наших поддеревьев уникальные. Значит, нам нужен здесь получается хэш, ключ которого — это сериализованное представление этого дерева. Вот и счётчик, сколько раз оно встречалось. Ну или можно иначе, наверное, там... То есть получается, в результатах мы должны, когда мы записываем, мы записываем ключ — это сериализованное, сериализованное представление этого дерева, и значение — это ссылка на собственно дерево. На одно из первых. Поэтому, когда мы находим новый дубликат, мы проверяем: в результатах уже такой есть по сериализованному варианту? Если нету, то добавляем. Если есть, тогда не добавляем. Тут тонкость сериализации, что нужно пустые элементы тоже отмечать, например, каким-то спецсимволом. Что ещё тут можно представить? То есть получается, у нас есть, когда мы проходим по поддеревьям, мы записываем каждое поддерево, сериализованное представление, в наш список, который уже есть. То есть там все уникальные, которые встретились, там присутствуют. То есть там должен быть ключ — это сериализованное представление, а значение — это связка: счётчик и ссылка на дерево. Получается так. Потому что чтобы мы его потом не искали, чтобы мы знали, где оно.

## Разбор

**Что верно:** пост-ордерная сериализация поддерева как ключ, hash со счётчиком и ссылкой на узел, добавление в ответ при достижении двух вхождений, маркер для nil — эталонный подход, включая тонкость про пустые узлы.

**Что упущено и ошибки:** не названа сложность (O(n²) в худшем случае на вырожденном дереве из-за конкатенации строк, память O(n)); не сказано, что добавлять нужно ровно при счётчике == 2, а не при каждом повторном вхождении; граничные случаи (n = 1 → []).

**Эталонная идея:** post-order обход: key = "#{val},#{left},#{right}" с "#" для nil; @map[key] += 1; res << node if @map[key] == 2.

**Сложность:** время O(n²) в худшем случае (на практике близко к O(n)), память O(n)

**Критерии:** идея ✅ · структура данных ✅ · сложность ❌ · граничные случаи ⚠️


**Разбор задачи:** [`../../algo-solutions/02-extra/05-tree/29-find-duplicate-subtrees.md`](../../algo-solutions/02-extra/05-tree/29-find-duplicate-subtrees.md)