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

Tree serialize / deserialize

O(n)

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

Elman HuseynovОбновлено 17 окт. 2026 г.

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

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

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

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

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

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

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

Источники: Википедия: Сериализация

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

Дерево в строку и обратно

deserialize(serialize(root)) // root = [1, 2, 3, null, null, 4, 5]

исходное дерево

записанные токены

пусто

Записываем дерево строкой в прямом порядке: узел, потом левое поддерево, потом правое. Отсутствующий потомок пишется как #.

1 / 25

Сериализация / десериализация дерева: шаблон кода

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();
}

interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}

function serialize(node: TreeNode | null): string {
    if (!node) return "#";
    return `${node.val},${serialize(node.left)},${serialize(node.right)}`;
}

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

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()

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;
}

    public static String serialize(TreeNode node) {
        if (node == null) return "#";
        return node.val + "," + serialize(node.left) + "," + serialize(node.right);
    }

    public static TreeNode deserialize(String data) {
        return build(new ArrayDeque<>(Arrays.asList(data.split(","))));
    }

    private static TreeNode build(Deque<String> vals) {
        String val = vals.poll();
        if (val == null || val.equals("#")) return null;
        TreeNode node = new TreeNode();
        node.val = Integer.parseInt(val);
        node.left = build(vals);
        node.right = build(vals);
        return node;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    public static string Serialize(TreeNode node) {
        if (node == null) return "#";
        return node.val + "," + Serialize(node.left) + "," + Serialize(node.right);
    }

    public static TreeNode Deserialize(string data) {
        return Build(new Queue<string>(data.Split(',')));
    }

    private static TreeNode Build(Queue<string> vals) {
        string val = vals.Dequeue();
        if (val == "#") return null;
        var node = new TreeNode();
        node.val = int.Parse(val);
        node.left = Build(vals);
        node.right = Build(vals);
        return node;
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

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

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

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

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

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

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

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();
}

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

Паттерн «Сериализация / десериализация дерева» нужен, когда в условии есть слова «сериализовать дерево в строку и десериализовать обратно», «восстановить точно ту же форму, а не только те же значения» или «формулировка encode/decode, разработать кодек для дерева». Решение на нём обычно укладывается в O(n).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Сериализация / десериализация дерева» чаще всего путают с этими паттернами: Обход дерева, Рекурсия, Обход графа BFS / DFS и Двоичное дерево поиска.

Обход дерева (Tree traversal): Обход только читает дерево. Сериализация ещё и записывает, где потомков нет.
Рекурсия (Recursion): Обе половины это обычная рекурсия. Вся работа в том, чтобы договориться о формате.
Обход графа BFS / DFS (Graph BFS / DFS): Формат по уровням не хуже, и его берут большинство сайтов с задачами. Читатель обязан совпасть с писателем.
Двоичное дерево поиска (Binary search tree): Дереву поиска метки не нужны, форму задаёт порядок. Обычному дереву они необходимы.

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

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

Паттерн «Сериализация / десериализация дерева» решает такие задачи с собеседований: Сериализация двоичного дерева, Сериализация дерева поиска, Сериализация n-арного дерева, Дерево по прямому и симметричному обходу, Дерево по прямому и обратному обходу, Поиск одинаковых поддеревьев и Кодирование и декодирование строк.

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