class Solution(object):
def __init__(self):
self.List = list() def rdfs(self,S):
if S != '':
length = len(S)
depth = len(self.List)
tempval = ''
tempdepth = 0
for i in range(length):
s = S[i]
if s != '-':
tempval += s
if i == length - 1:
while depth != tempdepth:
self.List.pop(-1)
depth = len(self.List)
parent = self.List[-1] val = int(tempval)
t = TreeNode(val)
if parent.left == None:
parent.left = t
elif parent.right == None:
parent.right = t else:
if tempval != '':
while depth != tempdepth:
self.List.pop(-1)
depth = len(self.List)
parent = self.List[-1] val = int(tempval)
t = TreeNode(val)
if parent.left == None:
parent.left = t
self.List.append(t)
self.rdfs(S[i:])
elif parent.right == None:
parent.right = t
self.List.append(t)
self.rdfs(S[i:])
break
else:
tempdepth += 1
else:
return None def recoverFromPreorder(self, S: str) -> 'TreeNode':
tempval = ''
length = len(S)
for i in range(length):
s = S[i]
if s != '-':#数字
tempval += s
if i == length - 1:
val = int(tempval)
root = TreeNode(val) else:#遇到横线，数字结束
val = int(tempval)
root = TreeNode(val)
self.List.append(root)
self.rdfs(S[i:])
self.List.pop(-1)
return root
return root