---
round: 3
ticket_no: 17
source_no: 26
slug: same-tree
topic: Tree
difficulty: Easy
leetcode_id: 100
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 17 — Same Tree

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

Даны корни двух бинарных деревьев `p` и `q`. Напишите функцию, которая проверяет, являются ли они одинаковыми.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны и узлы имеют одинаковые значения.

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

Constraints: количество узлов в каждом дереве находится в диапазоне `[0, 100]`; `-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/26-same-tree.md`](../../algo-solutions/02-extra/05-tree/26-same-tree.md)