---
title: "Сериализация / десериализация дерева"
url: https://algopath.pro/ru/patterns/tree-serialize
language: ru
summary: "Запишите дерево в одну плоскую строку и восстановите его точно таким же. Работает это за счёт меток отсутствующих потомков."
updated: 2026-08-24
---

# Сериализация / десериализация дерева

Запишите дерево в одну плоскую строку и восстановите его точно таким же. Работает это за счёт меток отсутствующих потомков.

## Сериализация / десериализация дерева: как это работает?

Выберите один порядок обхода и держитесь его. Из прямого обхода восстанавливать проще всего.

Записывайте значение узла в момент посещения. Разделяйте значения разделителем.

Записывайте метку и для каждого отсутствующего потомка. Без этих меток форма теряется.

При восстановлении читайте токены в том же порядке. Каждый токен даёт ровно один узел.

Метка означает пустого потомка, значит сразу возврат. Значение создаёт узел и читает двух его потомков.

Обе половины разбирают токены в одном порядке. Именно поэтому форма возвращается точно.

- `пишем 1` Дерево это 1 с левым потомком 2. Прямой обход пишет узел первым.
- `пишем 2` Следующим записывается левый потомок.
- `пишем #, #` У узла 2 потомков нет. Это записывают две метки.
- `пишем #` У узла 1 нет и правого потомка.
- `1,2,#,#,#` Пять токенов на два узла. Форму несут именно метки.

## Сериализация / десериализация дерева: когда применять?

- сериализовать дерево в строку и десериализовать обратно
- восстановить точно ту же форму, а не только те же значения
- формулировка encode/decode, разработать кодек для дерева
- маркеры null/None для отсутствующих детей
- сохранить или передать дерево (по сети, в файл, в кеш)

## Сериализация / десериализация дерева: с чем путают?

- **Обход дерева** - Обход только читает дерево. Сериализация ещё и записывает, где потомков нет.
- **Рекурсия** - Обе половины это обычная рекурсия. Вся работа в том, чтобы договориться о формате.
- **Обход графа BFS / DFS** - Формат по уровням не хуже, и его берут большинство сайтов с задачами. Читатель обязан совпасть с писателем.
- **Двоичное дерево поиска** - Дереву поиска метки не нужны, форму задаёт порядок. Обычному дереву они необходимы.

## Сериализация / десериализация дерева: сложность по времени и памяти

n узлов дают O(n) времени и O(n) на выход. Каждый узел и каждый отсутствующий потомок пишутся один раз.

## Сериализация / десериализация дерева: разбор примера

### Сериализовать и восстановить двоичное дерево

Превратите двоичное дерево в строку и верните из строки то же самое дерево.

Восстановленное дерево обязано совпасть с исходным узел в узел.

Пишите прямым обходом, ставя решётку на каждого пустого потомка.

Читайте обратно курсором по токенам. Решётка даёт null, всё остальное создаёт узел.

```javascript
function serialize(root) {
    const out = [];

    (function write(node) {
        if (!node) {
            out.push("#"); // the marker is what preserves the shape
            return;
        }
        out.push(String(node.val));
        write(node.left);
        write(node.right);
    })(root);

    return out.join(",");
}

function deserialize(data) {
    const tokens = data.split(",");
    let i = 0;

    function read() {
        const token = tokens[i++];
        if (token === "#") return null;

        const node = new TreeNode(Number(token));
        node.left = read();   // left must be consumed before right
        node.right = read();
        return node;
    }

    return read();
}
```

## Сериализация / десериализация дерева: частые ошибки

- **Не пишут метки** Один прямой обход не скажет, где потомка не было. Тогда два разных дерева дают одну строку.
- **Берут разделитель, встречающийся в данных** Значения бывают отрицательными и многозначными. Выберите символ, которого в значениях быть не может.
- **Восстанавливают по арифметике индексов** Это работает только на полном дереве. Используйте курсор, идущий по токенам.
- **Читают потомков в неверном порядке** Читатель обязан разобрать левого раньше правого. Некоторые языки вычисляют аргументы справа налево.

## Сериализация / десериализация дерева: задачи с собеседований

- **Сериализация двоичного дерева** Чистая форма, метка на каждого пустого потомка.
- **Сериализация дерева поиска** Метки не нужны, форму задаёт порядок значений.
- **Сериализация n-арного дерева** Пишите число потомков рядом с каждым значением.
- **Дерево по прямому и симметричному обходу** Два обхода задают форму без всяких меток.
- **Дерево по прямому и обратному обходу** Та же идея, но с одним неоднозначным случаем.
- **Поиск одинаковых поддеревьев** Сериализуйте каждое поддерево и посчитайте строки.
- **Кодирование и декодирование строк** Та же идея с префиксом длины, только для текста.

## JavaScript

```javascript
function serialize(node) {
    if (!node) return "#";
    return `${node.val},${serialize(node.left)},${serialize(node.right)}`;
}
function deserialize(data) {
    const vals = data.split(",");
    let i = 0;
    function build() {
        if (vals[i] === "#") { i++; return null; }
        const node = { val: Number(vals[i++]), left: null, right: null };
        node.left = build();
        node.right = build();
        return node;
    }
    return build();
}
```

## Python

```python
def serialize(node):
    if not node:
        return "#"
    return f"{node.val},{serialize(node.left)},{serialize(node.right)}"

def deserialize(data):
    vals = iter(data.split(","))
    def build():
        val = next(vals)
        if val == "#":
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node
    return build()
```

## PHP

```php
function serialize(?TreeNode $node): string {
    if ($node === null) return "#";
    return $node->val . "," . serialize($node->left) . "," . serialize($node->right);
}
function deserialize(array &$vals): ?TreeNode {
    $val = array_shift($vals);
    if ($val === "#") return null;
    $node = new TreeNode((int) $val);
    $node->left = deserialize($vals);
    $node->right = deserialize($vals);
    return $node;
}
```