Где применяется
1. Задача
У тебя в памяти лежит дерево: узлы, у каждого значение и ссылки на левого и правого ребёнка. Ты хочешь сохранить его в файл или отправить по сети, а потом загрузить обратно точно таким же деревом.
Файл или сетевое сообщение это плоская строка текста, а дерево ветвится. Ветвящуюся форму на диск напрямую не запишешь. Поэтому дерево превращают в одну строку текста (это сериализация), а позже читают эту строку и собирают из неё точно такое же дерево (это десериализация).
Главное, что нельзя потерять, это форму. Два разных дерева могут хранить одни и те же значения в одном и том же порядке. Например, 1 с левым ребёнком 2 и 1 с правым ребёнком 2: в прямом порядке оба дают 1, 2. Поэтому записать одни значения мало. Надо ещё отметить, где пустые места.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитdeserialize(serialize(root)) // root = [1, 2, 3, null, null, 4, 5]Записываем дерево строкой в прямом порядке: узел, потом левое поддерево, потом правое. Отсутствующий потомок пишется как #.
Как узнать
Эти слова в условии значат этот паттерн
- сериализовать дерево в строку и десериализовать обратно
- восстановить точно ту же форму, а не только те же значения
- формулировка encode/decode, разработать кодек для дерева
- маркеры null/None для отсутствующих детей
- сохранить или передать дерево (по сети, в файл, в кеш)
Похоже, но не то
- Обход дерева (Tree traversal)
Обход только читает дерево. Сериализация ещё и записывает, где потомков нет.
- Рекурсия (Recursion)
Обе половины это обычная рекурсия. Вся работа в том, чтобы договориться о формате.
- Обход графа BFS / DFS (Graph BFS / DFS)
Формат по уровням не хуже, и его берут большинство сайтов с задачами. Читатель обязан совпасть с писателем.
- Двоичное дерево поиска (Binary search tree)
Дереву поиска метки не нужны, форму задаёт порядок. Обычному дереву они необходимы.
n узлов дают O(n) времени и O(n) на выход. Каждый узел и каждый отсутствующий потомок пишутся один раз.
На LeetCode
Задачи, где дерево нужно превратить в строку и обратно или сравнить поддеревья по их записи. Записывай обход pre-order с меткой для каждого пустого ребёнка и читай обратно в том же порядке.
Обход pre-order со скобками вместо запятых, а пустая пара остаётся, только если за ней идёт правый ребёнок.
treeSerialize и treeDeserialize из урока под теми же именами.
Код урока работает, а в дереве поиска метки можно убрать и собирать из обхода pre-order с границами low и high.
Сериализуй каждое поддерево снизу вверх, считай строки в словаре и выдавай поддерево, когда его строка встретилась второй раз.