Easy to Understand Python Solution


  • 0
    Y
    class Solution(object):
        def str2tree(self, s):
            """
            :type s: str
            :rtype: TreeNode
            """
            if s == "":
                return None
            begin_of_left, root_val = self.get_int(0, s)
            root = TreeNode(root_val)
            left_tree_indices = self.get_tree_indices(begin_of_left, s)
            left_tree = self.str2tree(s[left_tree_indices[0]: left_tree_indices[1]])
            begin_of_right_tree = left_tree_indices[1] + 2
            end_of_right_tree = len(s) -1
            right_tree = self.str2tree(s[begin_of_right_tree: end_of_right_tree])
            root.left = left_tree
            root.right = right_tree
            return root
        
        def get_int(self, start_index, s):
            index = start_index
            while index < len(s) and s[index] not in "()":
                index += 1
            return index, int(s[start_index:index]) # returns the position after the int, as well as the int.
            
            
        
        def get_tree_indices(self, start_index, s):
            index = start_index
            left_count = right_count = 0
    
            while index < len(s):
                if s[index] == "(":
                    left_count += 1
                if s[index] == ")":
                    right_count += 1
                if left_count == right_count:
                    return start_index+1, index
                index += 1
            return start_index+1, index
                
           
    

  • 0
    Y

    Slightly shorter solution inspired by @awice

        def str2tree(self, s):
            # Find (, then find end of left tree. The right tree starts after that.
            begin_of_left = s.find("(")
            if begin_of_left < 0:
                # Either all num or none.
                return TreeNode(int(s)) if s else None
            # Now find the end of the left tree.
            paren_count = 0
            index = begin_of_left
            while index < len(s):
                if s[index] == "(":
                    paren_count +=1
                elif s[index] == ")":
                    paren_count -= 1
                if paren_count == 0:
                    break
                index += 1
                
            end_of_left = index
            left_indices = begin_of_left+1, end_of_left
            right_indices = end_of_left + 2, -1
            left_tree = self.str2tree(s[left_indices[0]: left_indices[1]])
            right_tree = self.str2tree(s[right_indices[0]: right_indices[1]])
            # Note that the left and right trees are without the () that wraps around them.
            root = TreeNode(int(s[:begin_of_left]))
            root.left = left_tree
            root.right = right_tree
            return root
    

Log in to reply
 

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