The problem
Design serialize, which turns a binary tree into a string, and deserialize, which turns that string back into exactly the same tree. Any format will do, as long as the round trip is exact.
Examples
01
- Input
root = [1, 2, 3, null, null, 4, 5]
- Output
[1, 2, 3, null, null, 4, 5]
02
- Input
root = []
- Output
[]
Constraints
- 0 ≤ number of nodes ≤ 10⁴
- −1000 ≤ Node.val ≤ 1000
The idea
Values alone lose the shape — 1, 2 could be 2 on either side of 1. Writing a marker # for every missing child keeps it.
Serialize in preorder: the value, then the whole left subtree, then the right, with # for each empty spot. Deserialize reads the tokens in the same order: a # is an empty tree; anything else is a node, whose left subtree is built from the tokens that follow, and then its right. Each call consumes exactly the tokens its subtree wrote.
- Time
- O(n) for both
- Space
- O(n) — the string
Solution · every language run against every case
class Codec: def serialize(self, root: Optional[TreeNode]) -> str: # Preorder, with "#" for every missing child: "1,2,#,#,3,4,#,#,5,#,#". out = [] def walk(node): if not node: out.append("#") return out.append(str(node.val)) walk(node.left) walk(node.right) walk(root) return ",".join(out) def deserialize(self, data: str) -> Optional[TreeNode]: # Read the tokens back in the same order: a node, then its whole left side, then its right. tokens = iter(data.split(",")) def build(): t = next(tokens) if t == "#": return None node = TreeNode(int(t)) node.left = build() node.right = build() return node return build()