Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard

Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде.
Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева.
Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.

Пример:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

👨‍💻 Алгоритм:

1⃣Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".

2⃣Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").

3⃣Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.

😎 Решение:

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Codec {
    rserialize(root, str) {
        if (root === null) {
            str.push("null");
        } else {
            str.push(String(root.val));
            this.rserialize(root.left, str);
            this.rserialize(root.right, str);
        }
    }

    serialize(root) {
        const str = [];
        this.rserialize(root, str);
        return str.join(",");
    }

    rdeserialize(data) {
        if (data[0] === "null") {
            data.shift();
            return null;
        }

        const root = new TreeNode(Number(data.shift()));
        root.left = this.rdeserialize(data);
        root.right = this.rdeserialize(data);
        return root;
    }

    deserialize(data) {
        const dataArray = data.split(",");
        return this.rdeserialize(dataArray);
    }
}

Ставь 👍 и забирай 📚 Базу знаний