# 1028. Recover a Tree From Preorder Traversal
We run a preorder depth first search on the root of a binary tree.
At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)
If a node has only one child, that child is guaranteed to be the left child.
Given the output S of this traversal, recover the tree and return its root.
Example 1:
Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
Example 2:
Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]
Example 3:
Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]
# Solution
Approach 1: iterative with a stack.
Approach 2: recursive -- consume the string along with the recursion.
# Code (Python)
Approach 1:
def recoverFromPreorder(self, string: str) -> TreeNode:
# iterative solution with a stack
if not string:
return None
# tokenize
splitted = string.split('-')
levels = [(0, int(splitted[0]))]
count = 1
for item in splitted[1:]:
if not item:
count += 1
else:
levels.append((count, int(item)))
count = 1
# construct the tree
root = TreeNode(levels[0][1])
stack = [(0, root)] # could also store just the nodes, and check levels using len(stack) because we only store 1 node per level
for item in levels[1:]:
while stack[-1][0] >= item[0]:
stack.pop()
node = TreeNode(item[1])
if stack[-1][1].left:
stack[-1][1].right = node
else:
stack[-1][1].left = node
stack.append((item[0], node))
return root
Approach 2:
def recoverFromPreorder(self, string):
# recursive solution
self.index = 0 # a global index that advances itself during the recursion
return self._construct(string, 0)
def _construct(self, string, expected_depth):
num_dashes = 0
while num_dashes + self.index < len(string) and string[self.index+num_dashes] == '-':
num_dashes += 1
# we get to a leaf or a node missing a subtree on the side
if num_dashes != expected_depth:
return None
digit_index = self.index + num_dashes
while digit_index < len(string) and string[digit_index] != '-':
digit_index += 1
root = TreeNode(int(string[self.index+num_dashes:digit_index]))
self.index = digit_index
root.left = self._construct(string, expected_depth + 1) # self.index advances itself after this operation
root.right = self._construct(string, expected_depth + 1)
return root
# Code (C++)
Approach 1:
Approach 2: