Description
Implement a codec that can reconstruct any binary tree, including missing children. Examples show deserialize(serialize(tree)) using level-order arrays.
Solution
import sys
sys.setrecursionlimit(100_000)
def serialize(root):
tokens = []
def visit(node):
if not node:
tokens.append('#')
return
tokens.append(str(node.val))
visit(node.left)
visit(node.right)
visit(root)
return ','.join(tokens)
def deserialize(data):
tokens = iter(data.split(','))
def build():
value = next(tokens)
if value == '#':
return None
node = TreeNode(int(value))
node.left = build()
node.right = build()
return node
return build()Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,null,2,3]]- Output
[1,null,2,3]
Null markers preserve the missing left child.
Example 2
- Input
[[]]- Output
[]
The null tree survives the round trip.
Example 3
- Input
[[-4]]- Output
[-4]
Negative values are serialized as signed tokens.
Approach
Serialize preorder values with explicit null markers, then recursively consume that same grammar.
Time & space
O(n) time; O(n) space including serialized tokens and recursion. Here n is the node count, and h is the tree height.