Naive solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverFromPreorder(self, S: str) -> TreeNode:
"""
tc O(N) sc O(N) N: len(S)
"""
level = 0
y = 0
i = 1
# get root number
for k in range(len(S)):
if S[k]!='-':
y = 10*y + int(S[k])
else:
i = k
break
n = len(S)
root = TreeNode(y)
st = [(root,0)]
while i < n:
# cnt level
if S[i] == '-':
level += 1
else:
# cnt node number
x,j = int(S[i]),i+1
while j < n and S[j] !='-':
x = 10*x +int(S[j])
i = j
j += 1
node = TreeNode(x)
# when current level way smaller than stack top
while level < st[-1][1]+1:
st.pop()
# when current level is bigger than stack top by 1 => child node
if level - st[-1][1] == 1:
#right node
if st[-1][0].left != None:
st[-1][0].right = node
else:
# left node
st[-1][0].left = node
#sibling node
elif level == st[-1][1]:
st.pop()
st[-1][0].right = node
st.append((node,level))
# print(st)
level = 0
i += 1
return root
Opmitimization: instead of caching level for each node in the stack, by comparing len(stack) to imply expected current level
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverFromPreorder(self, S: str) -> TreeNode:
"""
1.first count level, then count node val (order can't be changed )
2. chekc current level with len of stack, keep popping until len(stack) == level
3. check stack top if it has left child, if no => put node onto its left child ; otherwise check update its right child (must check st is not empty)
4. push new node onto stack
"""
level = i = 0
n,st = len(S),[]
while i < n:
val = 0
level = 0
# get level
while i < n and S[i] == '-':
level = level+1
i += 1
# get node val
while i < n and S[i] !='-':
val = 10*val +int(S[i])
i += 1
while len(st) > level:
st.pop()
node = TreeNode(val)
# (1) len(st) +1 == level => child node =>
# (2) len(st) == level => sibling node => st[-1].right
if st and st[-1].left is None:
st[-1].left = node
elif st:
st[-1].right = node
st.append(node)
return st[0]