Write a Codec class that can turn a binary tree into a string and turn that string back into the same tree:
serialize(root) takes the root of a binary tree and returns a string that describes it.deserialize(data) takes a string made by serialize and returns the root of a tree with the same shape and the same values as the original.The format of the string is entirely up to you. Use commas, brackets, a preorder walk, a level-order walk, anything, as long as deserialize can undo what serialize wrote.
How your code is judged. Only the round trip is checked, never the string itself. For each tree, the judge creates one Codec and calls its serialize, then creates a separate Codec and calls its deserialize on that string, and compares the tree that comes back with the one that went in. Since the two calls happen on different objects, everything deserialize needs must be in the string. Don't pass the tree between them through class-level, global or static variables.
Trees in the examples and tests are written level by level, left to right, with null for a missing child. The output is the tree your deserialize returned, written the same way, so a correct answer always equals the input.
One possible string is "6,-3,10,#,4,8,#,#,-7,#,#,#,#": the values level by level, with # for every missing child. Another is a preorder walk. Either is fine, provided your deserialize reads back what your serialize wrote.
Values can be negative and run to several digits, so the string has to show where one value ends and the next begins.
The root has only a right child, and that child has only a left child. Values can repeat, so the string must record which side each child hangs on, not just the values.
Constraints
0 and 10⁴ nodes. With 0 nodes, serialize gets None/null/nil and deserialize must give it back.-1000 <= Node.val <= 100010⁴ nodes is possible.A list of values alone can't tell different shapes apart. Write a marker for every missing child as well, and the shape is fully recorded.
Writing down the values isn't enough, because the same values fit many shapes. Take a root 1 with one child 2. Whether 2 hangs on the left or on the right, any walk you pick writes 1, 2. The string has to record the empty places too.
Time O(n)Space O(n)
The full walkthrough and code are part of Premium