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

O(n)

Закодировать дерево в строку (или массив), фиксируя каждого ребёнка, включая отсутствующих через специальный маркер, чтобы позже восстановить точно ту же форму.

Сигналы

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

Шаблон

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 для отсутствующих детей, чтобы восстановить именно структуру, а не только значения.

n узлов -> O(n) времени и O(n) длина результата: прямой обход с явными маркерами null записывает всю форму за один линейный проход и восстанавливает её за другой.

Изучить этот паттерн