LC 0536 [M] Construct Binary Tree from String - ALawliet/algorithms GitHub Wiki

kind of feels like valid parens problem

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def str2tree(self, s: str) -> TreeNode:
        stack = []
        num = ''
        root = None
        
        for i, c in enumerate(s):
            if c.isdigit() or c == '-':
                num += c
                
                # on last or next is not digit
                if i+1 == len(s) or not s[i+1].isdigit():
                    node = TreeNode(int(num))

                    if not root: # no root yet/stack is empty
                        root = node
                    else:
                        if not stack[-1].left:
                            stack[-1].left = node
                        else:
                            stack[-1].right = node

                    stack.append(node)
                    num = ''
                    
            elif c == '(':
                pass
            
            elif c == ')':
                stack.pop()

        return root