The order of numbers in the string is preorder. So we could construct this tree with preorder traversal.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import string
class Solution:
def str2tree(self, s: str) -> TreeNode:
self.s = s
self.index = 0
return self._helper()
def _helper(self):
if self.index >= len(self.s):
return None
tmp = ''
while self.index < len(self.s) and self.s[self.index] in (string.digits + '-'):
tmp += self.s[self.index]
self.index += 1
node = TreeNode(int(tmp))
# Add left subtree
if len(self.s) <= self.index:
return node
elif self.s[self.index] == '(':
self.index += 1
node.left = self._helper()
else:
self.index += 1
return node
# Add right subtree
if len(self.s) <= self.index:
return node
elif self.s[self.index] == '(':
self.index += 1
node.right = self._helper()
else:
self.index += 1
return node
if len(self.s) > self.index and self.s[self.index] == ')':
self.index += 1
return node