Read the text back into a tree
Rebuild a tree from its preorder text with markers, by reading entries one at a time and letting each node claim the next entries for its left and right subtrees. About 14 minutes.
Each call reads what it needs
Split the text at the commas into entries. Keep a position, shared by all calls. A call reads the entry at the position and moves the position forward by one.
If the entry is the hash sign, the subtree is empty, so return nothing. Otherwise it is a value: make a node with it, and then build its left subtree and its right subtree by calling the same function twice.
tokens = "1,#,2".split(",")
pos = 0
token = tokens[pos]
pos += 1- next
- 3
Read 5: a node. Build its left subtree from the entries that follow.
Left before right
The order of the two calls matters. The text lists the left subtree before the right one, so the left call must run first and consume its entries. After it returns, the position stands at the start of the right subtree.
When the outermost call returns, it has built the whole tree and has consumed every entry. The numbers are read as integers, and negative values need no special handling.
value = int(token) # "7" -> 7 is_gap = token == "#"
After the left subtree of a node is fully built, where does the shared position stand?
- AAt the first entry of the node's right subtree
- BBack at the start of the text
- CAt the end of the text
Show the answer
At the first entry of the node's right subtree. Each nested call consumed exactly its own entries.
Deserialize a binary tree
Design the reading half of a tree codec. Given a string data produced by writing a binary tree in preorder with # for each empty child and commas between entries, rebuild the tree and return its root. A string "#" gives an empty tree.
data = "1,2,#,#,3,4,#,#,5,#,#" → [1, 2, 3, null, null, 4, 5]
1 ≤ number of entries ≤ 20,001 · the text is valid · -1,000 ≤ node.val ≤ 1,000