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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте обратно курсором по токенам. Решётка даёт 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, разработать кодек для дерева
• •маркеры null/None для отсутствующих детей
• •сохранить или передать дерево (по сети, в файл, в кеш)

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

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

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

• Не пишут метки

  Один прямой обход не скажет, где потомка не было. Тогда два разных дерева дают одну строку.

• Берут разделитель, встречающийся в данных

  Значения бывают отрицательными и многозначными. Выберите символ, которого в значениях быть не может.

• Восстанавливают по арифметике индексов

  Это работает только на полном дереве. Используйте курсор, идущий по токенам.

• Читают потомков в неверном порядке

  Читатель обязан разобрать левого раньше правого. Некоторые языки вычисляют аргументы справа налево.

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

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

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

O(n)

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