---
round: 3
ticket_no: 12
source_no: 28
slug: subtree-of-another-tree
topic: Tree
difficulty: Easy
leetcode_id: 572
attempted: true
score:
verdict:
reviewed_at:
---

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

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

Даны корни двух бинарных деревьев `root` и `subRoot`. Верните `true`, если `subRoot` является поддеревом `root`.

Поддерево — это дерево, которое состоит из некоторого узла дерева `root` и всех его потомков. Дерево `root` также считается своим собственным поддеревом.

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

Constraints: количество узлов в дереве `root` находится в диапазоне `[1, 2000]`; количество узлов в дереве `subRoot` находится в диапазоне `[1, 1000]`; `-10^4 <= Node.val <= 10^4`.

## Ответ

> Здесь мы делаем механизм рекурсивного обхода нашего дерева. Проверяем, является ли левая часть равна нашему поддереву, либо правое равна поддереву. Ну и может быть, текущий элемент равен. То есть, как сравниваются два дерева, то есть, по факту, мы сравниваем голову, значение головы и лево-право. Ну, то есть они должны быть равны. То есть голову мы сравниваем, а дальше должны быть равны голова и значение, ну, как бы под деревьев. Когда мы в поддеревье уходим, опять же смотрится значение уже голов и так далее. Важно, что если два дерева равны, то тоже сохраняется, что одно является поддеревом другого. Так что здесь тоже нужно проверить равенство. Вот. Ну и, собственно, дальше мы это идём. Вот, если, ну, соответственно, где-то уже пустое значение, а в изначальном изначально оно не является. Сейчас, ну, значение там есть, то они как бы уже не равны. Здесь важно это тоже сравнить. Вот. Ну, не знаю, с точностью до лево-право, тут как можно. Вот. Понятное дело, что если у нас дерево представлено в массиве, то мы можем, может быть, как-то более эффективно пройти, если сравнить массивы. Вот, но дерево как объект такого доступа не даёт, поэтому нам нужно идти через его методы обхода.

## Разбор

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

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

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

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

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

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

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

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

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