All problems

Serialize and Deserialize Binary Tree

Hard · tree dfs

A game server needs to save a binary tree of scores into a single string, and later rebuild the same tree from that string. The string format is up to you. Design both halves inside your function: serialize(root) turns a tree into a string and deserialize(text) turns that string back into a tree.

Your function receives the root of a binary tree and must return deserialize(serialize(root)): a brand new tree with exactly the same shape and the same values as the original. Shape matters as much as values: a node that has only a right child is not the same as a node that has only a left child. An empty tree (one with no nodes) must come back as an empty tree.

Build new nodes while deserializing. Returning the nodes you were given, or keeping references to them, defeats the point: everything must pass through the string.

Examples

Example 1

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

Output: [1, 2, 3, null, null, 4, 5]

Node 1 has two children; node 3 has two children of its own, and 2 is a leaf.

Example 2

Input: root = [5, null, 8, 7]

Output: [5, null, 8, 7]

5 has only a right child, 8, and 8 has only a left child, 7. The tree must keep exactly that shape.

Example 3

Input: root = []

Output: []

An empty tree comes back as an empty tree.

Constraints