Tree to text and back
Files and network messages carry text, not objects. To save a tree or send it somewhere, a program turns it into a string. Turning a structure into text is called serializing it, and turning the text back into the structure is deserializing it.
Write a class Codec with two methods:
serialize(root)takes the root of a binary tree (aTreeNode, orNonefor an empty tree) and returns a string.deserialize(data)takes a string made byserializeand returns the root of a tree with the same shape and the same value at every position, built from newTreeNodeobjects. For an empty tree it returnsNone.
You choose the text format. The one rule is that deserialize(serialize(root)) rebuilds the tree. The string must carry everything: the tests serialize with one Codec and deserialize with another, so nothing may be kept outside the string. Values are integers, can be negative, and can repeat.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing. The output is the tree that deserialize rebuilds.
root = [4, 2, 6, None, 3]Output[4, 2, 6, None, 3]The rebuilt tree matches. One possible text is 4,2,6,N,3,N,N,N,N: the values row by row, with N for every missing child.
root = []Output[]An empty tree still becomes a string (for example N), and that string becomes None again.
root = [-7, 10, -7, None, None, 10]Output[-7, 10, -7, None, None, 10]Negative values, two-digit values and repeated values all come back in their places.
0 ≤ number of nodes ≤ 2 × 105
-1,000 ≤ node value ≤ 1,000, and values can repeat.
The tree is at most 500 levels deep.
serializeanddeserializerun on differentCodecobjects: the string is the only thing passed between them.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.