---
title: Find Duplicate Subtrees
difficulty: Medium
category: Tree (DFS + Hash)
leetcode_id: 652
revision_count: 1
last_revision: 2026-09-12
---

# Find Duplicate Subtrees

> **LeetCode:** [#652](https://leetcode.com/problems/find-duplicate-subtrees/)
> **Сложность:** Medium
> **Категория:** Tree (DFS + Hash)

## Условие

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

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

## Ключевая идея

Каждое поддерево однозначно представляется **строкой-сериализацией** (post-order: `val,left,right`, nil → маркер `#`). Проходим дерево снизу вверх, кладём сериализацию каждого поддерева в hash-map со счётчиком. Как только счётчик достигает **2** — это дубликат, добавляем узел в ответ (и больше не добавляем, даже если встретится 3-й раз).

## Оценка сложности

- **Время:** O(n²) в худшем случае — построение строки для каждого поддерева занимает O(размер поддерева); на вырожденном (скошенном) дереве суммарно O(n²). На практике почти всегда близко к O(n)
- **Память:** O(n) — хранение сериализаций в hash-map и рекурсивный стек O(h)

## Решение (Ruby)

```ruby
# Definition for a binary tree node.
# class TreeNode
#   attr_accessor :val, :left, :right
#   def initialize(val = 0, left = nil, right = nil)
#     @val = val
#     @left = left
#     @right = right
#   end
# end

# @param {TreeNode} root
# @return {TreeNode[]}
def find_duplicate_subtrees(root)
  counts = Hash.new(0)
  result = []

  serialize = lambda do |node|
    return '#' if node.nil?

    key = "#{node.val},#{serialize.call(node.left)},#{serialize.call(node.right)}"
    counts[key] += 1
    result << node if counts[key] == 2
    key
  end

  serialize.call(root)
  result
end
```

## Разбор на примере

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

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

Пост-ордер обход (левый подузел → правый подузел → сам узел):

step 1: узел 4 (нижний левый от двойки-справа): key="#,4,#" → count=1
step 2: узел 2 (справа, под 3): key="4,#,#,2,#"  → count=1
        (структура: val=2, left=4, right=nil)
step 3: узел 4 (слева от 2-в-корне): key="#,4,#" → count=2 → result=[4]  ← дубликат
step 4: узел 2 (слева в корне): key="4,#,#,2,#"  → count=2 → result=[4, 2]  ← дубликат
step 5: узел 4 (справа от 3): key="#,4,#" → count=3 → ничего (уже есть)
step 6: узел 3: key="4,4,#,#,3,#" → count=1
step 7: узел 1: key="2-#...,3-#...,1" → count=1

Результат: [узел 4, узел 2] → поддеревья [[4], [2, 4]]
```

## Edge Cases

- **root = nil / одно дерево без детей** → `[]`, дубликатов нет.
- **Все значения одинаковые, но структура разная** → сериализации разные (`#`-маркеры учитывают форму), дубликатов может не быть: `[2,2,2,3,null,3,null]` → поддеревья `[3]` и `[2,3]` по одному разу, дубликат только `[3]`? Нет — смотри пример 3: `[[2, 3], [3]]` — тут `[3]` встречается дважды (левый и правый ребёнок 2-в-корне... на самом деле `2,3`-узлы дублируются).
- **Один узел = поддерево**: одиночный узел тоже сериализуется и тоже может быть дубликатом (`[2,1,1]` → `[[1]]`).
- **Дубликат встречается 3+ раз** → в ответ попадает один раз (условие `counts[key] == 2`).

## Типичные ошибки

1. ❌ **Не учитывать nil-маркер `#`**: без него `[1,2]` (левый ребёнок) и `1,2` (правый ребёнок) дадут одинаковую строку — ложный дубликат. Маркер обязателен.
2. ❌ **Добавлять узел в ответ при каждом повторе**: проверка `== 2`, а не `>= 2` и не `> 0`, иначе узел попадёт в ответ несколько раз.
3. ❌ **Использовать pre-order без маркеров**: сериализация обязана полностью описывать форму дерева; любой обход без nil-маркеров теряет структуру.
4. ❌ **Сравнивать поддеревья попарно (brute-force)**: O(n²) сравнений с O(n²) памяти — проходит только на маленьких деревьях.
5. ❌ **Путать с Same Tree / Subtree**: здесь не проверяем одно поддерево на совпадение, а ищем все повторяющиеся структуры в одном дереве.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force: попарное сравнение всех поддеревьев | O(n² × m) | O(n) | для каждой пары запускаем is_same_tree — неприемлемо для больших деревьев |
| Сериализация + HashMap (строки) | O(n²) worst, ~O(n) avg | O(n) | **финальное решение** — простое и стандартное для интервью |
| Уникальные ID поддеревьев (Merkle-hash) | O(n) | O(n) | каждому поддереву назначаем целочисленный ID по тройке `(val, leftID, rightID)`; `O(n)` без тяжёлых строк. Сложнее, но global optimal |

Сериализация строкой — самый короткий и понятный вариант для интервью. ID-подход — ответ на вопрос «как убрать O(n²) в худшем случае».

## Заметки после повторения

_Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._