536. Construct Binary Tree from String

for this specific problem, it assumes there is no input like "4(2()(3))(6(5))" empty child

whenever finishing a number, build a node and push the node into stack
connect the node with the parent node in stack
this node could be either left or right child of the parent, depending on whether the parent has a left child already
when visiting a ), we know that we have finished the node already pushed to stack. We can pop it. if it is left child of parent, then evicting it could allow right child to be associated with parent. if it is right child, we can evict it anyway

class Solution:
    def str2tree(self, s: str) -> Optional[TreeNode]:
        stack = []
        i = 0
        while i < len(s):
            if s[i] == ')':
                stack.pop()
                i += 1
            elif s[i].isdigit() or s[i] == '-':
                start = i
                while i < len(s) and (s[i].isdigit() or s[i] == '-'):
                    i += 1
                num = int(s[start:i])
                node = TreeNode(num)

                if stack:
                    parent = stack[-1]
                    if not parent.left:
                        parent.left = node
                    else:
                        parent.right = node
                stack.append(node)
            else: # (
                i += 1
        
        return stack[0] if stack else None```

536. Construct Binary Tree from String - cocoder39/coco39_LC GitHub Wiki