LC 0536 [M] Construct Binary Tree from String
Code with Senpai edited this page Oct 11, 2022
·
8 revisions
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
footer