Python Recursive Solution


  • 0
    D
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def str2tree(self, s):
            """
            :type s: str
            :rtype: TreeNode
            """
            
            def construct(i, j):
                if i > j: return None
                i2 = i+1
                while i2 <= j and (s[i2]=='-' or s[i2].isdigit()): i2 += 1
                root = TreeNode(int(s[i:i2]))
                i = i2-1
                if i == j: return root
                left = 1
                k = i+3
                while k <= j and left > 0: 
                    if s[k] == '(': left += 1
                    if s[k] == ')': left -= 1
                    k += 1
                root.left = construct(i+2, k-2)
                root.right = construct(k+1, j-1)
                return root
            return construct(0, len(s) - 1)

Log in to reply
 

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