Сериализация и десериализация бинарного дерева

Сериализация и десериализация бинарного дерева

Это задача на обход дерева и восстановление структуры. Нам нужно сохранить информацию о дереве в строку так, чтобы потом можно было восстановить исходное дерево полностью, включая пустые узлы.

Ключевые концепции

Сериализация — преобразование объекта (дерево) в строку для хранения или передачи.

Десериализация — восстановление объекта из строки.

Трудность: обычный обход (inorder, postorder) не содержит информацию о пустых узлах, поэтому нельзя уникально восстановить дерево.

Решение: Preorder обход с null маркерами

Мы используем предпорядковый обход (preorder) и добавляем маркеры для пустых узлов:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    def serialize(self, root):
        """
        Кодирует дерево в строку.
        Используем preorder обход: корень, левое поддерево, правое поддерево
        """
        result = []
        
        def preorder(node):
            if not node:
                result.append("null")
                return
            
            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return ",".join(result)
    
    def deserialize(self, data):
        """
        Декодирует строку обратно в дерево
        """
        nodes = data.split(",")
        self.index = 0
        
        def build():
            val = nodes[self.index]
            self.index += 1
            
            if val == "null":
                return None
            
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        
        return build()

Пошаговое выполнение

Дерево:
    1
   / \
  2   3
     / \
    4   5

Шаг 1: Сериализация (preorder)
Порядок обхода: 1 → 2 → null → null → 3 → 4 → null → null → 5 → null → null

Детально:
  1. Посетить 1 (добавить 1)
  2. Левое от 1 (узел 2)
     a. Посетить 2 (добавить 2)
     b. Левое от 2 → null (добавить null)
     c. Правое от 2 → null (добавить null)
  3. Правое от 1 (узел 3)
     a. Посетить 3 (добавить 3)
     b. Левое от 3 (узел 4)
        i. Посетить 4 (добавить 4)
        ii. Левое от 4 → null (добавить null)
        iii. Правое от 4 → null (добавить null)
     c. Правое от 3 (узел 5)
        i. Посетить 5 (добавить 5)
        ii. Левое от 5 → null (добавить null)
        iii. Правое от 5 → null (добавить null)

Результат: "1,2,null,null,3,4,null,null,5,null,null"

Шаг 2: Десериализация
Индекс = 0, nodes = [1, 2, null, null, 3, 4, null, null, 5, null, null]

build():
  val = nodes[0] = 1 → создаём TreeNode(1)
  index = 1
  left = build():
    val = nodes[1] = 2 → создаём TreeNode(2)
    index = 2
    left = build():
      val = nodes[2] = null → return None
    index = 3
    right = build():
      val = nodes[3] = null → return None
    index = 4
    return TreeNode(2)
  index = 4
  right = build():
    val = nodes[4] = 3 → создаём TreeNode(3)
    index = 5
    left = build():
      val = nodes[5] = 4 → создаём TreeNode(4)
      index = 6
      left = build():
        val = nodes[6] = null → return None
      index = 7
      right = build():
        val = nodes[7] = null → return None
      index = 8
      return TreeNode(4)
    index = 8
    right = build():
      val = nodes[8] = 5 → создаём TreeNode(5)
      index = 9
      left = build():
        val = nodes[9] = null → return None
      index = 10
      right = build():
        val = nodes[10] = null → return None
      index = 11
      return TreeNode(5)
    index = 11
    return TreeNode(3)

Полная реализация с тестами

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Codec:
    """
    Сериализует и десериализует дерево
    Сложность: O(n) для обоих операций
    """
    
    def serialize(self, root):
        """
        Преобразует дерево в строку через preorder обход
        """
        result = []
        
        def preorder(node):
            if not node:
                result.append("null")
                return
            
            result.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
        
        preorder(root)
        return ",".join(result)
    
    def deserialize(self, data):
        """
        Восстанавливает дерево из строки
        """
        nodes = data.split(",")
        self.index = 0
        
        def build():
            if self.index >= len(nodes):
                return None
            
            val = nodes[self.index]
            self.index += 1
            
            if val == "null":
                return None
            
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
        
        return build()

# Тестирование
if __name__ == "__main__":
    codec = Codec()
    
    # Создаём дерево
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(5)
    
    # Сериализуем
    serialized = codec.serialize(root)
    print(f"Сериализовано: {serialized}")
    # Вывод: 1,2,null,null,3,4,null,null,5,null,null
    
    # Десериализуем
    deserialized = codec.deserialize(serialized)
    print(f"Десериализовано")
    
    # Проверяем
    reserialized = codec.serialize(deserialized)
    print(f"Повторно сериализовано: {reserialized}")
    print(f"Совпадает: {serialized == reserialized}")

Альтернатива: Уровневый обход (Level order)

from collections import deque

def serialize_level_order(root):
    if not root:
        return ""
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        if not node:
            result.append("null")
        else:
            result.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
    
    return ",".join(result)

def deserialize_level_order(data):
    if not data:
        return None
    
    nodes = data.split(",")
    root = TreeNode(int(nodes[0]))
    queue = deque([root])
    i = 1
    
    while queue and i < len(nodes):
        node = queue.popleft()
        
        # Левый потомок
        if nodes[i] != "null":
            node.left = TreeNode(int(nodes[i]))
            queue.append(node.left)
        i += 1
        
        # Правый потомок
        if i < len(nodes) and nodes[i] != "null":
            node.right = TreeNode(int(nodes[i]))
            queue.append(node.right)
        i += 1
    
    return root

Уровневый обход более эффективен по памяти для несбалансированных деревьев.

Сравнение подходов

Сложность

• Временная: O(n) для обхода всех узлов
• Пространственная: O(n) для хранения строки и рекурсивного стека

Предпорядковый обход с null маркерами — это классический подход для сериализации деревьев, который гарантирует уникальное восстановление структуры.