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

# Symmetric Tree

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

## Условие

Дан корень бинарного дерева `root`. Вернуть `true`, если дерево **симметрично относительно своего центра** — т.е. является зеркальным отражением самого себя.

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

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

Сводим задачу к **зеркальному сравнению дерева с самим собой**: `is_mirror(root, root)` — корень сравнивается сам с собой, и дальше левое поддерево идёт против правого. Два узла зеркальны, если их значения равны, левый ребёнок первого зеркален правому ребёнку второго, а правый ребёнок первого зеркален левому ребёнку второго (обход крест-накрест, а не один в один). Приём «сравнить объект с самим собой» заодно закрывает пустое дерево: `is_mirror(nil, nil)` → `true` без отдельного guard-условия.

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

- **Время:** O(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} root
# @return {Boolean}
def is_symmetric(root)
  is_mirror(root, root)  # сравниваем дерево с самим собой: nil-корень даёт true без отдельной ветки
end

def is_mirror(left, right)
  return true if left.nil? && right.nil?

  return false if left.nil? || right.nil? || left.val != right.val

  is_mirror(left.left, right.right) && is_mirror(left.right, right.left)
end
```

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

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

step 0: is_mirror(root=1, root=1) → один и тот же узел, значения равны → крест-накрест:
        is_mirror(1.left=2, 1.right=2)
        is_mirror(1.right=2, 1.left=2) — вторая ветка дублирует первую
step 1: is_mirror(2, 2) → значения равны → крест-накрест:
        is_mirror(2.left=3, 2.right=3)
        is_mirror(2.right=4, 2.left=4)
step 2: is_mirror(3, 3) → равны, дети nil → true
step 3: is_mirror(4, 4) → равны, дети nil → true
Результат: true && true = true
```

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

step 0: is_mirror(root=1, root=1) → крест-накрест:
        is_mirror(1.left=2, 1.right=2)
step 1: is_mirror(2, 2) → значения равны → крест-накрест:
        is_mirror(2.left=nil, 2.right=3)
        is_mirror(2.right=3, 2.left=nil)
step 2: is_mirror(nil, 3) → один nil → false
Результат: false (вторую ветку даже не проверяем — короткое замыкание)
```

## Edge Cases

- **Пустое дерево** (`root = nil`) → `true`: пустое дерево симметрично. `is_mirror(nil, nil)` даёт `true` — отдельный guard не нужен
- **Один узел** (`[1]`) → `true`: `is_mirror(root, root)` → далее `is_mirror(nil, nil)`
- **Оба ребёнка корня nil** — покрывается предыдущим случаем
- **Дерево с одним ребёнком** (`[1, 2]`) → `false`: `is_mirror(2, nil)`
- **Симметричные значения, но разная форма** (`[1,2,2,3]` — у левой 2 есть ребёнок 3, у правой нет) → `false`
- **Зеркально одинаковые структуры с разными значениями** → `false`

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

1. ❌ **Сравнивать поддеревья один в один** (как в Same Tree): `is_mirror(left.left, right.left)`. Для симметрии обход идёт **крест-накрест**: `left.left` ↔ `right.right`, `left.right` ↔ `right.left`.
2. ❌ **Забыть базовый случай «оба nil»**: без него рекурсия упадёт с `nil.val` (NoMethodError).
3. ❌ **Проверять значения до nil-проверок**: сначала оба nil → true, потом один nil → false, и только потом сравнение значений — иначе исключение.
4. ❌ **Обращаться к `root.left` без проверки**: если `root` — nil (пустое дерево — валидный вход), `root.left` упадёт с NoMethodError. Приём `is_mirror(root, root)` закрывает это без guard-ветки.
5. ❌ **Итеративная сериализация с BFS**: уровневый обход с null-маркерами и проверка, что каждая строка уровней — палиндром. Работает, но длиннее и сложнее рекурсии.

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

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

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

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

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