---
title: Same Tree
difficulty: Easy
category: Tree (DFS)
leetcode_id: 100
revision_count: 1
last_revision: 2026-09-12
---

# Same Tree

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

## Условие

Даны корни двух бинарных деревьев `p` и `q`. Вернуть `true`, если деревья **структурно идентичны** (одинаковая форма) и значения всех соответствующих узлов равны.

```
Input: p = [1, 2, 3], q = [1, 2, 3]  →  Output: true
Input: p = [1, 2],    q = [1, null, 2]  →  Output: false
Input: p = [1, 2, 1], q = [1, 1, 2]  →  Output: false
```

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

Рекурсивный DFS: на каждом уровне сравниваем текущие узлы (оба `nil` → ок; один `nil` или разные значения → `false`), затем рекурсивно сравниваем левых и правых детей. Деревья равны, только если равны корни, левые поддеревья и правые поддеревья.

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

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

## Решение (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} p
# @param {TreeNode} q
# @return {Boolean}
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: p = [1, 2, 3], q = [1, 2, 3]

step 1: p.val=1, q.val=1, равно → идём влево
step 2: p.left=2, q.left=2, равно → у обоих children=nil:
        is_same_tree(nil, nil) → true (оба nil)
step 3: p.right=3, q.right=3, равно → дети nil → true
Результат: true && true = true
```

```
Input: p = [1, 2], q = [1, null, 2]  (p: 1→left 2; q: 1→right 2)

step 1: p.val=1, q.val=1, равно → идём влево
step 2: p.left=2, q.left=nil → один nil → false (структура разная)
Результат: false (правое поддерево даже не проверяем — короткое замыкание)
```

## Edge Cases

- **Оба дерева пустые** (`nil`, `nil`) → `true`: валидные, структурно идентичны
- **Одно дерево пустое, другое нет** → `false`, форма разная
- **Деревья разной глубины** (`[1, 2]` vs `[1, null, 2]`) → `false`, хотя значения частично совпадают
- **Дубликаты значений в разных местах** (`[1, 2, 1]` vs `[1, 1, 2]`) → `false`: значения одинаковые, но структура разная
- **Самое простое дерево** (`[0]`, `[0]`) → `true`

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

1. ❌ **Проверять только значения, игнорируя структуру**: `p.val == q.val` без проверки детей → `[1, 2]` vs `[1, null, 2]` даст неверный `true`.
2. ❌ **Забыть базовый случай «оба nil»**: без него рекурсия упадёт с `nil.val` (NoMethodError).
3. ❌ **Забыть про короткое замыкание / порядок проверок**: сначала проверяем nil-кейсы, потом сравниваем значения — иначе `nil.val` вызовет исключение.
4. ❌ **Сравнивать по предпорядковому обходу со списком значений**: `[1, 2]` и `[1, null, 2]` в preorder дают `[1, 2]` и `[1, 2]` — ложное равенство. Нужен обход с учётом null, либо просто рекурсивное сравнение.

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

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| **Рекурсивный DFS (сравнение узлов)** | **O(n)** | **O(h)** | **финальное решение — простое, читаемое, стандарт для интервью** |
| Итеративный BFS/DFS со стеком или очередью | O(n) | O(n) | то же по времени, больше кода; полезно, если хотят избежать рекурсии (глубокие деревья) |
| Сравнение сериализаций (preorder с null-маркерами) | O(n) | O(n) | работает, но длиннее и проще ошибиться |

Рекурсивный подход — самый короткий и естественный для деревьев. Итеративный вариант нужен только при риске переполнения стека на очень глубоких деревьях.

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

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