Hardtreedesign
Решить задачу Serialize and Deserialize Binary Tree (LeetCode 297)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 297. Сериализация binary tree в string и обратно. DFS pre-order с null markers. Стандарт для интервью.
def serialize(root):
if not root:
return 'null'
return f'{root.val},{serialize(root.left)},{serialize(root.right)}'
def deserialize(data):
values = iter(data.split(','))
def build():
val = next(values)
if val == 'null':
return None
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()Сериализация: pre-order traversal, null для пустых. Десериализация: тот же order восстанавливает структуру. Альтернатива — BFS уровень за уровнем. Важно: восстанавливает идентичное дерево, не эквивалентное. Связанные: Serialize BST (449) — компактнее без null markers (BST property), N-ary Tree (428) — marker для конца детей.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.