Binary Trees Building and serializing
380. Serialize and Deserialize Binary Tree
Design a way to turn a binary tree into a string, and to build the same tree back from that string. Write a
class Codec with two methods:
serialize(root)takes the root of a binary tree and returns a string.deserialize(data)takes a string thatserializereturned and returns the root of the tree it describes.
The string can look however you like. Only the tree that deserialize returns is checked: it must have the
same shape and the same values as the tree that was serialized. deserialize must build that tree from the
string alone, out of new nodes. It cannot use anything that serialize saved, such as a field, and it cannot
return nodes of the original tree.
In C# the methods are Serialize and Deserialize. Go creates a codec with Constructor(), and Rust with
Codec::new().
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out. The output shows the tree that deserialize returns the
same way.
Example 1
Input: root = [3, 1, 8, null, 2, 5, 9, null, null, 4]
[3,1,8,null,2,5,9,null,null,4]Explanation: Any string works, as long as deserialize rebuilds this exact tree from it. 2 must come back as the right
child of 1, and 4 as the left child of 5.
Example 2
Input: root = []
[]Explanation: The empty tree must come back as an empty tree.
Example 3
Input: root = [-1, 0, -1, null, -1]
[-1,0,-1,null,-1]Explanation: Values can be negative and can repeat. Three nodes hold -1, and each one must come back in its own place.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.