Python Clean Solution

  • 0

    The only thing I want to note is that the time complexity for this algorithm is O(N^2) when the tree is a linked-list. It goes through N characters in the first recursion, N-1 in the second recursion and N-2, N-3 ... in the following recursions which sum up to N^2 operations, totally.

    class Solution(object):
        def str2tree(self, s):
            :type s: str
            :rtype: TreeNode
            if s:
                cnt = start = 0
                root = None
                for i, c in enumerate(s):
                    if c == "(":
                        if not root and cnt == 0:
                            root = TreeNode(s[:i])
                        cnt += 1
                        if cnt == 1:
                            start = i + 1
                    if c == ")":
                        cnt -= 1
                        if cnt == 0:
                            if not root.left:
                                root.left = self.str2tree(s[start:i])
                                root.right = self.str2tree(s[start:i])
                return root if root else TreeNode(s)

Log in to reply

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