Serialize and Deserialize Binary Tree
Design an algorithm to serialize a binary tree to a string and deserialize it back.
Input: level-order array (comma-separated, 'null' for missing). Output: serialized then deserialized back to level-order.
Return the recovered tree's level-order values as a single string separated by spaces, with 'null' for missing children and trailing 'null' entries omitted. Return an empty string for an empty tree.
Example
1,2,3,null,null,4,5
1 2 3 null null 4 5
- Input:
1,2,3,null,null,4,5lists the tree level by level, left to right; eachnullis an empty child slot. Root 1 has children 2 and 3, node 2 has none, and node 3 has children 4 and 5: 5 nodes on 3 levels. - The round trip: the string encoding is your choice, but it must be lossless. If the two empty slots under 2 were lost, 4 and 5 would be rebuilt as children of 2 and the shape would change.
- Output: the rebuilt tree, listed level by level with single spaces, is
1 2 3 null null 4 5: 7 entries, 5 values plus the 2 empty slots under 2. - Notice that the 4 empty child slots under 4 and 5 are omitted, since nothing follows them. That is why the tree
1,2prints just1 2. - Here the output is just the input with commas turned into spaces, because this input has no trailing empty slots.
Constraints
- 0 <= number of nodes <= 10^4
- -1000 <= Node.val <= 1000