Construct Binary Tree from String

Intuition

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import string


class Solution:
    def str2tree(self, s: str) -> TreeNode:
        self.s = s
        self.index = 0
        return self._helper()

    def _helper(self):
        if self.index >= len(self.s):
            return None

        tmp = ''
        while self.index < len(self.s) and self.s[self.index] in (string.digits + '-'):
            tmp += self.s[self.index]
            self.index += 1
        node = TreeNode(int(tmp))

        # Add left subtree
        if len(self.s) <= self.index:
            return node
        elif self.s[self.index] == '(':
            self.index += 1
            node.left = self._helper()
        else:
            self.index += 1
            return node

        # Add right subtree
        if len(self.s) <= self.index:
            return node
        elif self.s[self.index] == '(':
            self.index += 1
            node.right = self._helper()
        else:
            self.index += 1
            return node

        if len(self.s) > self.index and self.s[self.index] == ')':
            self.index += 1
        return node