Serialize and Deserialize Binary Tree

To save a binary tree in a file, you first turn it into text. This is called serializing the tree. Building the same tree back from the text is deserializing it.

Write the class Codec with two methods:

• serialize(root) gets the root of a binary tree and returns a string. The tree may be empty.
• deserialize(data) gets a string that serialize returned. It returns the root of the same tree, with the same shape and values.

You decide what the string looks like. Each test serializes with one Codec object and deserializes with another. So everything must be inside the string.

The tests print the rebuilt tree row by row from the top. Each row goes left to right. A missing child is written as null. The nulls at the end are left out. The examples write trees the same way.

Your starter code spells the class and method names the way your language does.

Example 1:

Input: root = [6,2,9,null,4,7]
Output: [6,2,9,null,4,7]
       6
      / \
     /   \
    2     9
     \   /
      4 7

Explanation: The rebuilt tree is the same as the input.
One string that works lists the nodes in preorder.
It writes # for each missing child:
"6,2,#,4,#,#,9,7,#,#,#"

Example 2:

Input: root = []
Output: []
Explanation: An empty tree needs a string too.
With the format above, that string is "#".
It must turn back into an empty tree.

Example 3:

Input: root = [-15,300]
Output: [-15,300]
  -15
  /
300

Explanation: A value can have a minus sign and several digits.
So the string needs a separator between values:
"-15,300,#,#,#"
This reads back as -15 and 300, not as single characters.

Constraints:

• The tree has 0 to 200,000 nodes.
• Each value is a whole number from -1,000 to 1,000.
• The tree is at most 400 levels deep.