Medium Preorder Advanced Trees
In plain English: Convert a binary tree to a string so it can be saved, then rebuild the tree from that string.
Preorder traversal with null markers uniquely identifies a tree. Serialize: visit, left, right. Deserialize: read values and recurse, using an iterator.
Prompt
Serialize a binary tree to a string and deserialize it back to the original tree structure.
Try to write it from scratch before scrolling down.
Solution
class Codec:
def serialize(self, root):
vals = []
def preorder(node):
if not node:
vals.append('#') # null marker so structure is unambiguous
return
vals.append(str(node.val))
preorder(node.left)
preorder(node.right)
preorder(root)
return ','.join(vals)
def deserialize(self, data):
# iterator lets recursive calls consume tokens in order without index bookkeeping
vals = iter(data.split(','))
def build():
v = next(vals)
if v == '#':
return None
node = TreeNode(int(v))
node.left = build()
node.right = build()
return node
return build()
# Test: tree [1,2,3] => "1,2,#,#,3,#,#" => back to tree