---
title: Subtree of Another Tree
difficulty: Easy
category: Tree (DFS)
leetcode_id: 572
revision_count: 1
last_revision: 2026-09-12
---

# Subtree of Another Tree

> **LeetCode:** [#572](https://leetcode.com/problems/subtree-of-another-tree/)
> **Сложность:** Easy
> **Категория:** Tree (DFS)

## Условие

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

```
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
```

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

Комбинация двух рекурсивных обходов: (1) проходим по `root` в поисках узла, значение которого совпадает с корнем `subRoot`; (2) для каждого кандидата запускаем `is_same_tree` (LeetCode 100 — Same Tree). Если хоть один кандидат совпал — `true`.

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

- **Время:** O(m × n) в худшем случае — для каждого из n узлов `root` может потребоваться полное сравнение с `subRoot` (m узлов)
- **Память:** O(h) — глубина рекурсивного стека; h = max(height(root), height(subRoot))

## Решение (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
# @param {TreeNode} sub_root
# @return {Boolean}
def is_subtree(root, sub_root)
  return false if root.nil?
  return true if is_same_tree(root, sub_root)

  is_subtree(root.left, sub_root) || is_subtree(root.right, sub_root)
end

def is_same_tree(p, q)
  return true if p.nil? && q.nil?
  return false if p.nil? || q.nil? || p.val != q.val

  is_same_tree(p.left, q.left) && is_same_tree(p.right, q.right)
end
```

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

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

step 1: root.val=3, subRoot.val=4 → не равно → is_same_tree(3, 4) → false
step 2: идём влево root.left=4; root.left.val=4 == subRoot.val=4 → запускаем is_same_tree
        is_same_tree(4, 4): 4==4 → идём влево
            4.left=1, subRoot.left=1: 1==1 → дети nil → true
            4.right=2, subRoot.right=2: 2==2 → дети nil → true
        is_same_tree → true
Результат: true (нашли поддерево с корнем 4)
```

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

step 1: root.val=3, subRoot.val=4 → false → идём влево
step 2: root.left=4, val=4 → запускаем is_same_tree
        is_same_tree(4, 4): 4==4 → идём влево
            4.left=1, subRoot.left=1: 1==1 → дети nil → true
            4.right=2, subRoot.right=2: 2==2 → идём влево
                2.left=0, subRoot.right.left=nil → один nil → false
        is_same_tree(4, 4) → false
step 3: root.right=5, val=5 ≠ 4 → false
Результат: false (поддерево с корнем 4 включает лишний узел 0)
```

## Edge Cases

- **subRoot = nil** → по условию задачи `nil` не считается поддеревом (ожидается `false`). LeetCode гарантирует непустое `subRoot`.
- **root = nil** → `false`, поддерева нет.
- **Оба дерева совпадают целиком** → `true`, `is_same_tree(root, subRoot)` сработает на первом же вызове.
- **subRoot — один узел, присутствует в root** → `true`.
- **Все значения в root и subRoot одинаковые, но структура разная** → `false` (same tree отловит несовпадение).

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

1. ❌ **Забыть рекурсивный обход root**: если проверять только корень, пропустим поддерево глубже.
2. ❌ **Путать с Same Tree**: `is_same_tree` — это часть решения, а не вся задача. Нужен внешний обход.
3. ❌ **Проверять только значения, а не структуру**: `subRoot` может совпадать по значениям, но отличаться по форме.
4. ❌ **Не останавливаться при первом совпадении**: `||` в `is_subtree` даёт короткое замыкание — как только нашли `true`, рекурсия прекращается.

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

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| **Рекурсивный DFS + Same Tree** | **O(m × n)** | **O(h)** | **финальное решение — простое, читаемое, стандарт** |
| Сериализация + KMP (поиск подстроки) | O(m + n) | O(m + n) | хитрый: сериализуем деревья (preorder с null-маркерами), ищем subRoot-строку в root-строке через KMP. Быстрее, но сложнее |
| Хеширование поддеревьев (Merkle hash) | O(m + n) | O(m + n) | каждому поддереву вычисляем хеш, сравниваем хеши. Надёжно, но требует хеш-функции без коллизий (или двойного хеширования) |

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

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

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