---
round: 1
ticket_no: 19
source_no: 28
slug: subtree-of-another-tree
topic: Tree
difficulty: Easy
leetcode_id: 572
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 19 — Subtree of Another Tree

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

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

```
Input:  root = [3,4,5,1,2], subRoot = [4,1,2]  →  true
```

## Ответ

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

## Разбор

**Что верно:** две рекурсии: сравнение деревьев на полное совпадение и обход root с запуском этого сравнения в каждом узле — эталонная идея.

**Что упущено и ошибки:** не названа сложность O(m·n) и не сказано, что на интервью обычно просят улучшить решение (сериализация + hash/KMP); граничные случаи (subRoot = nil, root = nil) не разобраны.

**Эталонная идея:** is_subtree(root, sub) = same(root, sub) || is_subtree(root.left, sub) || is_subtree(root.right, sub), где same — сравнение деревьев.

**Сложность:** время O(m·n) в худшем случае, память O(h)

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


**Разбор задачи:** [`../../algo-solutions/02-extra/05-tree/28-subtree-of-another-tree.md`](../../algo-solutions/02-extra/05-tree/28-subtree-of-another-tree.md)