# Construct Binary Tree from String

## Intuition

The order of numbers in the string is preorder. So we could construct this tree with preorder traversal.

## Solution

``````
# 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))

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

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

``````