Design a class Codec with two methods: serialize(root) turns a binary tree into a string, and deserialize(data) turns that string back into the exact same tree. You may choose any string format, as long as deserializing a serialized tree gives back an identical tree. The judge checks deserialize(serialize(root)).
- The number of nodes is in the range 0 to 10^4
- -1000 <= Node.val <= 1000
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A single traversal of values cannot rebuild a tree (two different trees can share a preorder list), and storing two traversals like preorder plus inorder breaks when values repeat. The fix is to record the empty children too. With null markers, the preorder sequence becomes unambiguous: when decoding, every token either closes a branch (#) or starts a new node whose left and right subtrees follow immediately. Both directions visit each node once.
Algorithm
- serialize: run preorder DFS. Append the value for a node and
#for null, separated by commas. - deserialize: split the string by commas into a queue of tokens.
- Define
build(): take the next token. If it is#, return null. - Otherwise create a node with that value, set
left = build(), thenright = build(), and return it.
O(n) for both methodsSpace: O(n) for the string and recursion12 versus 1 and 2 become impossible to tell apart.class Codec: def serialize(self, root: Optional[TreeNode]) -> str: out = [] def write(node): if node is None: out.append("#") # marker for a missing child return out.append(str(node.val)) write(node.left) write(node.right) write(root) return ",".join(out) def deserialize(self, data: str) -> Optional[TreeNode]: tokens = iter(data.split(",")) def read(): t = next(tokens) if t == "#": return None node = TreeNode(int(t)) node.left = read() # preorder: left subtree comes next node.right = read() return node return read()