---
round: 3
ticket_no: 4
source_no: 29
slug: find-duplicate-subtrees
topic: Tree
difficulty: Medium
leetcode_id: 652
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 04 — Find Duplicate Subtrees

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

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

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

Constraints: количество узлов в дереве находится в диапазоне `[1, 5000]`; значения узлов — `0 <= Node.val <= 200`.

## Ответ

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

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

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

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

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