Serialize and Rebuild a Tree

A tree has to be stored in a text file and read back later. Write two functions:

• serialize(root) turns a binary tree into a string (any format you like).
• deserialize(data) turns such a string back into a tree with exactly the same shape and values.

Only the round trip is tested: tree_to_list(deserialize(serialize(root))) must equal tree_to_list(root). An empty tree must survive the round trip too, and values may be negative.

Examples

    1
   / \
  2   3
     / \
    4   5

Input:  root = build_tree([1, 2, 3, None, None, 4, 5])
Output: tree_to_list(deserialize(serialize(root))) == [1, 2, 3, None, None, 4, 5]

Input:  root = build_tree([])
Output: tree_to_list(deserialize(serialize(root))) == []

Constraints

• 0 <= number of nodes <= 1000
• -1000 <= node.val <= 1000
• serialize must return a str

Goals

• Design a text encoding that records missing children explicitly
• Consume an encoded stream with a recursive parser that rebuilds the same shape