Simple recursive Python


  • 0

    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
    

  • 0
    C

    @realisking what is the complexity?


  • 0

    @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.


Log in to reply
 

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