LC 0536 [M] Construct Binary Tree from String
Code with Senpai edited this page Dec 21, 2021
·
8 revisions
kind of feels like valid parens problem
# 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):
c = s[i]
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
footer