Модуль 21 ⏱ ~14 мин чтения 📐 1 Mermaid диаграмм

7. Serialize and Deserialize Binary Tree

«Формат данных переживает код, который его создал; проектируйте его так, будто он останется навсегда».
— Брайан Керниган

Сериализация и десериализация бинарного дерева: проектирование протоколов и строковая инженерия

Задача проектирования алгоритма сериализации и десериализации бинарного дерева (Serialize and Deserialize Binary Tree, LeetCode 297) венчает раздел алгоритмических задач.
В отличие от задач на вычисление одного числового ответа, здесь проверяется системный инженерный дизайн:

  • Сериализация: преобразование древовидной структуры в компактную строку или поток байтов.
  • Десериализация: однозначное, детерминированное восстановление исходной структуры дерева из строки.

В распределенных бэкенд-системах этот процесс лежит в основе сетевых протоколов (gRPC / Protocol Buffers, JSON RPC), передачи деревьев выражений в SQL-оптимизаторах и персистентного сохранения деревьев состояний на диск.

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    subgraph Serialization["Сериализация: Preorder DFS"]
        A["Корень node"]:::entry --> B{"node == nil ?"}:::warning
        B -->|"Да"| C["Записать маркер '#,'"]:::process
        B -->|"Нет"| D["Записать 'val,'"]:::process
        D --> E["Рекурсия для node.Left"]:::process
        E --> F["Рекурсия для node.Right"]:::process
    end

    subgraph Deserialization["Десериализация: Посимвольный парсинг"]
        G["Чтение следующего токена"]:::entry --> H{"token == '#' ?"}:::warning
        H -->|"Да"| I["Вернуть nil"]:::process
        H -->|"Нет"| J["Создать TreeNode(val)"]:::process
        J --> K["node.Left = Десериализация"]:::process
        K --> L["node.Right = Десериализация"]:::process
        L --> M["Вернуть восстановленный узел"]:::success
    end

1. Архитектура протокола: почему одного обхода обычно недостаточно?

В классической теории деревьев (1. Теория. Деревья) известно: чтобы однозначно восстановить бинарное дерево по значениям узлов, требуются два обхода (например, Preorder + Inorder).
Однако если мы сохраняем маркеры пустых указателей (Nil / Null Sentinel), например символ #, то дерево однозначно восстанавливается всего по одному Preorder (или Postorder) обходу!

Сравнение форматов обхода:

  1. Preorder DFS (Корень → Лево → Право):
    Самый лаконичный и естественный формат. Десериализация строится через прямую рекурсию без очередей.
  2. BFS (Поуровневый обход):
    Использует очередь. Удобен для потокового чтения без глубокого рекурсивного стека вызовов, но требует хранения очередей в памяти.

2. Идиоматичная реализация на Go: Zero-Allocation парсинг

Наивный подход использует strings.Split(data, ","). Это порождает огромный срез строк в куче, создавая двойное потребление памяти.
В промышленной реализации мы используем:

  • strings.Builder для линейной конкатенации строки сериализации.
  • Посимвольный парсинг по указателю смещения pos для десериализации (срезы строк без выделения памяти).
Go 
package treecodec

import (
    "strconv"
    "strings"
)

// TreeNode представляет узел бинарного дерева
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// Codec инкапсулирует логику кодирования и декодирования
type Codec struct{}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (c *Codec) Serialize(root *TreeNode) string {
    var sb strings.Builder
    c.buildString(root, &sb)
    return sb.String()
}

func (c *Codec) buildString(node *TreeNode, sb *strings.Builder) {
    if node == nil {
        sb.WriteString("#,")
        return
    }

    sb.WriteString(strconv.Itoa(node.Val))
    sb.WriteByte(',')

    c.buildString(node.Left, sb)
    c.buildString(node.Right, sb)
}

// Deserializes your encoded data to tree.
func (c *Codec) Deserialize(data string) *TreeNode {
    if len(data) == 0 {
        return nil
    }
    pos := 0
    return c.buildTree(data, &pos)
}

func (c *Codec) buildTree(data string, pos *int) *TreeNode {
    if *pos >= len(data) {
        return nil
    }

    // Извлекаем следующий токен до запятой за O(1) памяти
    start := *pos
    for *pos < len(data) && data[*pos] != ',' {
        *pos++
    }
    token := data[start:*pos]
    *pos++ // пропускаем разделительную запятую

    if token == "#" {
        return nil
    }

    val, err := strconv.Atoi(token)
    if err != nil {
        return nil
    }

    node := &TreeNode{Val: val}
    node.Left = c.buildTree(data, pos)
    node.Right = c.buildTree(data, pos)

    return node
}

3. Аппаратная эффективность и механика строк в Go

Zero-Copy срезы строк

В коде token := data[start:*pos] не происходит копирования символов.
В рантайме Go строка представляется структурой StringHeader:

Go 
type StringHeader struct {
    Data unsafe.Pointer
    Len  int
}

Срез строки лишь сдвигает указатель Data и изменяет Len. Он живет в регистрах процессора и не аллоцируется в куче.

Преимущества strings.Builder

Вызов оператора + для строк выделяет новую строку в куче на каждом шаге ($O(N^2)$ аллокаций).
strings.Builder использует внутренний байтовый буфер []byte, удваивающийся геометрически, что гарантирует амортизированное линейное время $O(N)$ и минимальную фрагментацию памяти.

4. Вопросы для собеседования

Резюме

  1. Добавление маркеров пустых узлов (#) позволяет восстановить структуру дерева всего по одному обходу.
  2. Использование strings.Builder и посимвольного извлечения токенов исключает ненужные аллокации памяти в рантайме Go.
  3. Механическая симпатия проявляется в использовании zero-copy срезов строк, что делает сериализатор масштабируемым под высокие нагрузки.

🎓 Завершение Модуля 21: Вы готовы к собеседованиям любого уровня

Вы прошли колоссальный путь через 29 фундаментальных кластеров и 247 лекций:

  • От базовых трюков со слайсами и указателями до параллельных графовых обходов и динамического программирования.
  • От системных структур данных (LRU/LFU, Swiss Tables, Min-Heap) до потоковых вероятностных скетчей (HyperLogLog, Count-Min, $P^2$).
  • Вы овладели не просто академическими алгоритмами, а механической симпатией к рантайму Go, ядру Linux и архитектуре современных процессоров.

Теперь любые алгоритмические секции уровня Middle, Senior и Lead — это не препятствие, а возможность продемонстрировать инженерное превосходство. В добрый путь!