# 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 tree2str(self, t: TreeNode) -> str:
"""
tc O(N) sc O(N)
1. 4 cases: (1)both left right child (2)no children (3) has only left child (4*) has only right child
"""
res = []
def pre(node):
if not node:
return
# preorder traversal
res.append(str(node.val))
if node.left:
res.append('(')
pre(node.left)
res.append(')')
if node.right:
if not node.left:
res.append('()')
res.append('(')
pre(node.right)
res.append(')')
pre(t)
return ''.join(res)
stack
# 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 tree2str(self, t: TreeNode) -> str:
if not t :
return ""
st = [t]
seen = set()
res = []
while st:
node = st[-1]
if node in seen:
st.pop()
res.append(")")
else:
seen.add(node)
res.append('(')
res.append(str(node.val))
if not node.left and node.right:
res.append('()')
if node.right:
st.append(node.right)
if node.left:
st.append(node.left)
return ''.join(res[1:-1])