Serialize and Deserialize Binary Tree: preorder с маркерами, BFS как в LeetCode и BST без null

Разбор задачи Serialize and Deserialize Binary Tree: preorder с маркерами null, BFS-формат LeetCode, компактный вариант для BST без маркеров, сложность и ошибки на собеседовании.

12 мин чтенияалгоритмы · деревья · рекурсия · python

Коротко

Вопрос	Ответ
Что нужно	Превратить дерево в строку и восстановить из строки точно такое же дерево
Главная идея	Записывать не только значения, но и пустых детей: маркер `#` для каждого `None`
Базовое решение	Preorder (корень, левое, правое) с маркерами, восстановление тем же обходом по итератору
Альтернатива	BFS по уровням — формат `[1,2,3,null,null,4,5]`, которым LeetCode описывает тесты
Сложность	$O(n)$ по времени и памяти в обе стороны
Если дерево — BST	Маркеры не нужны: хватает одного preorder, границы $(low, high)$ сами показывают, где пусто

Serialize and Deserialize Binary Tree — задача 297 на LeetCode с пометкой Hard. Пугаться не стоит: алгоритмически это обычный обход дерева, сложность в другом. Нужно самому придумать формат данных и доказать, что он однозначный. На собеседовании это быстро показывает, понимает ли кандидат, какую информацию теряет обход, и умеет ли он писать парные функции, которые не расходятся в деталях. Если обходы в глубину ещё не уложились в голове, начните со статьи про preorder, inorder и postorder.

Условие

Нужно написать класс Codec с двумя методами:

serialize(root) — получает корень бинарного дерева и возвращает строку;
deserialize(data) — получает эту строку и возвращает корень дерева, совпадающего с исходным по структуре и значениям.

Формат строки вы выбираете сами. Проверяющая система вызывает deserialize(serialize(root)) и сравнивает результат с оригиналом. Ограничения на LeetCode: до $10^4$ узлов, значения от $-1000$ до $1000$ . Значит, в узлах бывают отрицательные и многозначные числа, а дерево может выродиться в цепочку глубиной 10 000.

Пример дерева, на котором разберём все способы:

Почему одного обхода мало

Первая мысль — выписать значения в каком-нибудь порядке. Preorder даёт 1 2 3 4 5. Но по этой последовательности дерево не восстановить: 1 2 может быть корнем с левым ребёнком 2, а может — с правым. Обход фиксирует порядок посещения узлов, но не говорит, где у дерева пустые места.

Есть классический обходной путь: preorder вместе с inorder задают дерево однозначно (задача LeetCode 105, Construct Binary Tree from Preorder and Inorder Traversal). Для сериализации он плох по двум причинам. Во-первых, строка выходит в два раза длиннее. Во-вторых, метод работает только при уникальных значениях: если в дереве три узла со значением 7, по inorder не понять, какая из семёрок корень. В задаче 297 уникальность значений не обещана.

Поэтому правильный ход — явно записывать пустые места. Каждый None становится маркером, например #. Тогда последовательность сама описывает форму дерева.

Решение 1: preorder с маркерами null

Обходим дерево в порядке корень → левое поддерево → правое поддерево. Для существующего узла пишем значение, для отсутствующего — #. Разделитель — запятая.

Для нашего дерева получится:

1,2,#,#,3,4,#,#,5,#,#

Читается это так: корень 1; его левый ребёнок 2; у двойки нет ни левого, ни правого (#,#); дальше правый ребёнок единицы — 3; у тройки левый 4 без детей, правый 5 без детей.

Восстановление — тот же обход, только вместо чтения дерева мы читаем токены. Берём очередной токен: если это #, возвращаем None; иначе создаём узел и рекурсивно строим ему сначала левое поддерево, потом правое. Порядок вызовов в точности повторяет порядок записи, поэтому каждый токен попадает на своё место.

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):
        out = []

        def dfs(node):
            if node is None:
                out.append('#')
                return
            out.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ','.join(out)

    def deserialize(self, data):
        tokens = iter(data.split(','))

        def build():
            token = next(tokens)
            if token == '#':
                return None
            node = TreeNode(int(token))
            node.left = build()
            node.right = build()
            return node

        return build()

Ключевая деталь — iter(...) и next(...). Все рекурсивные вызовы делят один курсор по списку токенов, поэтому не нужно передавать индекс и возвращать его обратно. В языках без итераторов то же самое делается через общий индекс: поле класса или переменную в замыкании.

Пустое дерево сериализуется в строку #, и deserialize('#') честно возвращает None. Отдельной ветки для этого случая не нужно, и это хороший признак, что формат выбран удачно.

Почему формат однозначный

Можно показать по индукции. Строка для пустого дерева — ровно один токен #. Строка для непустого дерева — значение корня, за которым идёт строка левого поддерева, а за ней строка правого. Когда build() читает левое поддерево, он по предположению индукции съедает ровно его токены и останавливается, не залезая в правое. Значит, граница между поддеревьями определяется однозначно и запятые с маркерами не путаются.

Полезный факт для самопроверки: в дереве из $n$ узлов ровно $n + 1$ маркеров #. У $n$ узлов $2n$ ссылок на детей, из них $n - 1$ заняты рёбрами, остальные $n + 1$ пустые. Для нашего примера: 5 узлов, 6 решёток.

То же на JavaScript

На фронтенд-собеседованиях задачу часто просят на JS. Итераторов из коробки в таком стиле не пишут, поэтому используем общий индекс в замыкании:

function serialize(root) {
  const out = []
  const dfs = (node) => {
    if (node === null) {
      out.push('#')
      return
    }
    out.push(String(node.val))
    dfs(node.left)
    dfs(node.right)
  }
  dfs(root)
  return out.join(',')
}

function deserialize(data) {
  const tokens = data.split(',')
  let i = 0
  const build = () => {
    const token = tokens[i++]
    if (token === '#') return null
    const node = new TreeNode(Number(token))
    node.left = build()
    node.right = build()
    return node
  }
  return build()
}

Решение 2: без рекурсии

Ограничение в $10^4$ узлов и дерево-цепочка дают глубину рекурсии 10 000. Стандартный лимит Python — 1000 кадров, так что рекурсивная версия на вырожденном дереве упадёт с RecursionError, если не поднять sys.setrecursionlimit. На LeetCode лимит обычно уже поднят, но на собеседовании полезно сказать об этом вслух и показать итеративный вариант.

Сериализация — обычный preorder со стеком. Правого ребёнка кладём раньше левого, чтобы левый достался первым. None тоже кладём в стек, чтобы при снятии записать маркер:

def serialize_iter(root):
    out, stack = [], [root]
    while stack:
        node = stack.pop()
        if node is None:
            out.append('#')
            continue
        out.append(str(node.val))
        stack.append(node.right)
        stack.append(node.left)
    return ','.join(out)

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

def deserialize_iter(data):
    tokens = data.split(',')
    if tokens[0] == '#':
        return None
    root = TreeNode(int(tokens[0]))
    # в стеке — узел и какой ребёнок у него следующий: 0 — левый, 1 — правый
    stack = [[root, 0]]
    for token in tokens[1:]:
        node = None if token == '#' else TreeNode(int(token))
        parent = stack[-1]
        if parent[1] == 0:
            parent[0].left = node
            parent[1] = 1
        else:
            parent[0].right = node
            stack.pop()
        if node is not None:
            stack.append([node, 0])
    return root

Обе функции дают тот же формат, что и рекурсивная версия, поэтому их можно смешивать. Я проверял это на нескольких тысячах случайных деревьев и на цепочке из 5000 узлов — строки совпадают, деревья восстанавливаются.

Решение 3: BFS, как в LeetCode

LeetCode в условиях задач рисует деревья как [1,2,3,null,null,4,5]. Это обход по уровням: узлы выписываются слева направо уровень за уровнем, отсутствующие дети — null. Про сам обход есть отдельная статья, здесь важны две особенности формата.

Дети null не записываются. Это не массив кучи, где ребёнок узла $i$ лежит на позиции $2i + 1$ . Если у узла нет детей, в очередь он ничего не добавляет, и позиции дальнейших узлов сдвигаются. Иначе для цепочки из 20 узлов пришлось бы хранить около миллиона null.
Хвостовые null обрезаются. У листьев 4 и 5 в нашем дереве четыре пустых ребёнка, но в строке их нет.

from collections import deque


def serialize_bfs(root):
    if root is None:
        return '[]'
    out, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            out.append('null')
            continue
        out.append(str(node.val))
        queue.append(node.left)
        queue.append(node.right)
    while out[-1] == 'null':
        out.pop()
    return '[' + ','.join(out) + ']'


def deserialize_bfs(data):
    values = data.strip('[]').split(',') if data != '[]' else []
    if not values:
        return None
    root = TreeNode(int(values[0]))
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if values[i] != 'null':
            node.left = TreeNode(int(values[i]))
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] != 'null':
            node.right = TreeNode(int(values[i]))
            queue.append(node.right)
        i += 1
    return root

При восстановлении очередь хранит узлы, которым ещё не раздали детей. Из очереди берём узел и читаем для него два значения подряд: левого и правого ребёнка. Из-за обрезанного хвоста строка может закончиться посреди уровня, поэтому перед чтением правого ребёнка стоит проверка i < len(values). Без неё на [1,2] получится IndexError.

serialize_bfs на нашем дереве возвращает [1,2,3,null,null,4,5] — ровно то, что показывает LeetCode. Этот же код удобно держать под рукой для локальных тестов: копируете массив из условия, получаете дерево.

Какой формат выбрать

Критерий	Preorder с `#`	BFS как в LeetCode
Объём кода	Меньше, обе функции зеркальны	Больше, есть граничные случаи
Память при обходе	$O(h)$ — высота дерева	$O(w)$ — ширина уровня
Риск переполнения стека	Есть у рекурсии	Нет
Читаемость человеком	Средняя	Привычная по LeetCode

На собеседовании я бы писал preorder: он короче, и корректность легко обосновать. BFS стоит упомянуть как альтернативу и сказать, что он не упирается в глубину рекурсии.

Вариант для BST: без маркеров

Задача LeetCode 449, Serialize and Deserialize BST, просит сделать строку как можно компактнее. Здесь маркеры не нужны: для бинарного дерева поиска форму задаёт само упорядочивание значений.

Сериализуем обычный preorder без #. Для BST, собранного вставками 5, 3, 8, 1, 4, 9, получится 5 3 1 4 8 9.

При восстановлении передаём в рекурсию допустимый диапазон $(low, high)$ . Корень может быть любым. Его левое поддерево принимает только значения меньше корня, правое — только больше. Если очередное значение в диапазон не попадает, значит, это поддерево пустое и значение принадлежит кому-то выше.

def serialize_bst(root):
    out = []

    def dfs(node):
        if node:
            out.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

    dfs(root)
    return ' '.join(out)


def deserialize_bst(data):
    values = [int(x) for x in data.split()]
    i = 0

    def build(low, high):
        nonlocal i
        if i == len(values) or not (low < values[i] < high):
            return None
        node = TreeNode(values[i])
        i += 1
        node.left = build(low, node.val)
        node.right = build(node.val, high)
        return node

    return build(float('-inf'), float('inf'))

Разберём 5 3 1 4 8 9. Корень 5, диапазон левого поддерева $(-\infty, 5)$ . Тройка в него попадает — левый ребёнок. Левое поддерево тройки $(-\infty, 3)$ : единица подходит. Левое поддерево единицы $(-\infty, 1)$ : четвёрка не подходит, пусто; правое $(1, 3)$ — тоже не подходит, пусто. Возвращаемся к тройке, её правое $(3, 5)$ : четвёрка подходит. Восьмёрка не лезет ни в одно поддерево внутри $(-\infty, 5)$ , поэтому всплывает до корня и становится его правым ребёнком.

Каждое значение читается один раз, а на каждый узел приходится не больше трёх вызовов build, так что всё работает за $O(n)$ . Наивный вариант — для каждого корня искать, где кончается левое поддерево, линейным проходом — даёт $O(n^2)$ на вырожденном дереве. Та же техника решает задачу LeetCode 1008, Construct Binary Search Tree from Preorder Traversal.

Хотите ещё компактнее — пишите числа не текстом, а байтами фиксированной длины: в задаче 449 значения не больше $10^4$ , хватает двух байт на узел. На собеседовании обычно достаточно сказать, что так можно.

Осторожно с дубликатами

Строгое неравенство low < values[i] < high рассчитано на уникальные значения. Если в дереве есть повторы, нужно договориться, куда идут равные. Например, при правиле «равные — вправо» строгая версия на дереве 2 → 2 (корень и правый ребёнок с тем же значением) потеряет второй узел: двойка не попадёт ни в $(-\infty, 2)$ , ни в $(2, \infty)$ . Исправление — полуинтервал: условие low <= values[i] < high. Левое поддерево получает $[low, val)$ , правое — $[val, high)$ , и повторы встают на место.

Разбор сложности

Пусть $n$ — число узлов, $h$ — высота дерева.

Способ	Время	Доп. память	Длина строки
Preorder с `#`, рекурсия	$O(n)$	$O(h)$ стек + $O(n)$ строка	$2n + 1$ токенов
Preorder с `#`, стек	$O(n)$	$O(h)$ + $O(n)$	$2n + 1$ токенов
BFS	$O(n)$	$O(w)$ очередь + $O(n)$	до $2n + 1$ , хвост обрезан
BST без маркеров	$O(n)$	$O(h)$ + $O(n)$	$n$ токенов

В худшем случае $h = n$ (цепочка), в сбалансированном дереве $h = O(\log n)$ . Ширина $w$ у полного дерева — около $n/2$ , у цепочки — 1. Сама строка всегда $O(n)$ , меньше не получится: нужно хотя бы записать все значения.

Типичные ошибки

Нет разделителя. Строка 1234 без запятых — это 1,2,3,4 или 12,34? С многозначными и отрицательными числами без разделителя не обойтись. Если очень хочется без разделителя, нужна фиксированная ширина поля.

Разделитель есть, но маркер совпадает со значением. Если записывать пустой узел как 0 или -1, всё сломается на дереве, где такое значение реально встречается. Маркер должен быть вне множества допустимых значений.

Конкатенация строк в цикле. s += str(val) + ',' в Java или C# создаёт новую строку на каждой итерации — $O(n^2)$ в худшем случае. Собирайте список и делайте join или используйте StringBuilder.

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

split на пустой строке. Если пустое дерево сериализовать в '', то ''.split(',') в Python вернёт [''], а не пустой список. Отсюда маркер # и для пустого дерева — граничный случай исчезает.

BFS как массив кучи. Попытка класть детей на позиции $2i+1$ и $2i+2$ ломается, как только у null нет детей, а формат LeetCode их не пишет.

Глобальное состояние. Если индекс курсора хранится в поле объекта Codec, а не локально в вызове, второй вызов deserialize на том же объекте начнёт не с нуля. Проверяющая система LeetCode может переиспользовать объект.

Как говорить об этом на собеседовании

Хороший порядок ответа:

Сразу сказать, почему одного обхода не хватает, и привести контрпример из двух узлов.
Предложить preorder с маркерами и объяснить однозначность: каждое поддерево — это значение и две подстроки, $n + 1$ маркер.
Написать две функции, прогнать вслух на дереве из 4–5 узлов.
Назвать сложность и упомянуть глубину рекурсии на цепочке.
Если останется время — BFS-формат и вариант для BST без маркеров.

Частые продолжения от интервьюера: «а если дерево N-арное?» — пишем значение и число детей, потом самих детей (LeetCode 428). «А если нужно найти одинаковые поддеревья?» — сериализуем каждое поддерево, складываем строки в хеш-таблицу и ищем повторы (LeetCode 652, Find Duplicate Subtrees). То есть сериализация — это ещё и способ получить канонический ключ для структуры.

Больше задач на деревья с разбором — в подборке задач на деревья, а если хочется освежить, чем отличаются обходы в глубину и в ширину, — в статье про DFS и BFS.

Потренироваться в спокойной обстановке

Все задачи