259/670

259. Serialize and Deserialize Binary Tree

Hard

A binary tree lives in memory as linked nodes, but to store it in a file or send it over a wire it has to become a flat sequence of characters — and later come back to life as the exact same tree.

Write the two halves of that pipeline:

serialize(root) — receives the root node (or nothing, for an empty tree) and returns a single string encoding the whole tree.
deserialize(data) — receives a string produced by your serialize and returns the root of a reconstructed tree with the same shape and the same values everywhere.

The encoding is entirely your design — the judge never inspects your string. It builds a tree from the test input, pipes it through serialize then deserialize, and checks the reconstructed tree node by node. The only contract is that your two functions agree with each other.

Each node has an integer val and left/right child pointers; the TreeNode type is already defined for you.

Preorder encoding with null sentinelsSerializing the tree in preorder, writing # wherever a child is missing. The sentinels (gold) pin down the shape, so the token stream can be decoded back into exactly one tree.

Example 1:

Input: deserialize(serialize(root)) where root = [1,2,3,null,null,4,5]

Output: a tree identical to root

Explanation: The tree has root 1, left child 2 (a leaf), and right child 3 with children 4 and 5. Whatever string serialize produces, deserialize must rebuild exactly this tree, so the judge prints the same level-order form it was given.

Example 2:

Input: deserialize(serialize(None))

Output: None (the empty tree)

Explanation: The empty tree must survive the round trip too: serialize receives no nodes, and deserialize must hand back an empty tree.

Constraints:

0 ≤ number of nodes ≤ 10⁴
-1000 ≤ Node.val ≤ 1000
The string fed to deserialize is always one produced by your own serialize.

Hints:

A plain traversal order (preorder, level order…) is not enough by itself — [1,2] as left child and [1,2] as right child would look identical. Record where the missing children are with an explicit sentinel token such as #.

Preorder with null sentinels is uniquely decodable: the first token is the root, then the left subtree's tokens, then the right subtree's. Deserialize by consuming tokens with the same recursion that produced them.

Prefer an iterator/queue over the token list to an index you pass around by hand — the recursion consumes exactly the tokens that belong to each subtree, so no bookkeeping of positions is needed.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: root = [1, 2, 3, null, null, 4, 5]

Expected output: [1, 2, 3, null, null, 4, 5] (round trip preserved)