# Simple recursive Python

• The idea is simple, first we find the root value, then we begin to count the `brackets`, add one when we find a `"("` and minus one when we find a `")"`. When `brackets == 0`, we have a complete `left sub tree` for root, and the rest is the `right sub tree`.

``````class Solution(object):
def str2tree(self, s):
"""
:type s: str
:rtype: TreeNode
"""
if not s: return None
i = 0
while i < len(s) and (s[i].isdigit() or s[i] == "-"): i += 1
root = TreeNode(int(s[:i]))
start, brackets, i = i+1, 1, i+1
while brackets and i < len(s):
brackets += 1 if s[i] == "(" else -1 if s[i] == ")" else 0
i += 1
root.left = self.str2tree(s[start:i-1])
root.right = self.str2tree(s[i+1:-1])
return root
``````

• @realisking what is the complexity?

• @Chengcheng.Pei
The original code can be O(n^2) since slicing in Python takes O(n). We can easily transfer into O(n) via using indices instead of slicing the string. But it was during the contest so I choose to keep it simple.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.