Serialize and Deserialize Binary Tree

Serialization changes a data structure into a string. You can then store the string or send it to another computer. Deserialization changes the string back into the original data structure.

Design a way to serialize and deserialize a binary tree. In a binary tree, each node has at most two children: a left child and a right child.

Write the class Codec with two methods. serialize(root) takes the root of a tree and returns a string. deserialize(data) takes such a string and returns the root of a tree.

You choose the string format. The only rule is that deserialize must build the same tree again from the string that serialize returns. The test uses one Codec object to serialize and a different Codec object to deserialize.

The examples show each tree as a list in level order. This list gives the nodes row by row, from left to right. The value null marks a missing child. Each output is the tree that deserialize returns.