Serialize and Deserialize Binary Tree
Serialize and Deserialize Binary Tree is a hard Trees problem from the Blind 75. The key pattern is level-order encoding, and a good solution runs in O(n) time.
Problem
Round-trip the trimmed level-order representation of a binary tree and print the reconstructed representation.
Examples
Example 1
Input
[1,2,3,null,4,null,5]Output
[1,2,3,null,4,null,5]Example 2
Input
[1]Output
[1]Example 3
Input
[5,4,7,3,null,2,null,-1,null,9]Output
[5,4,7,3,null,2,null,-1,null,9]Approach
Write nodes breadth-first with explicit markers for missing children, and rebuild them in the same order with a queue.
| Pattern | Level-order encoding |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
Trim trailing empty markers so the printed form matches the expected representation.