# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# inorder traversal
# version 1, traversal solution
def tree2str(root):
    """
    :type root: TreeNode
    :rtype: str
    """
    tree2str.res = ""
    def helper(root):
        if not root:
            return
        if not root.left and not root.right: # if no child
            tree2str.res += str(root.val)
            return

        tree2str.res += str(root.val)
        if root.left:
            tree2str.res += '('
            helper(root.left)
            tree2str.res += ')'
        else:
            tree2str.res += '()'
        if root.right:
            tree2str.res += '('
            helper(root.right)
            tree2str.res += ')'
    helper(root)
    return tree2str.res
# version 2, divide conquer solution
def tree2str(root):
    """
    :type root: TreeNode
    :rtype: str
    """
    def helper(node):
        if not node:
            return ''
        if not node.left and not node.right:
            return str(node.val)

        root = str(node.val)
        if node.left:
            root += '(' + helper(node.left) + ')'
        else:
            root += '()'
        if node.right:
            root += '(' + helper(node.right) + ')'
        return root
    return helper(root)

class Solution(object):
    def tree2str(self, t):
        """
        :type t: TreeNode
        :rtype: str
        """
        res = []
        def dfs(root):
            if not root:
                return
            res.append(str(root.val))
            if root.left or root.right:
                res.append('(')
                dfs(root.left)
                res.append(')')
            if root.right:
                res.append('(')
                dfs(root.right)
                res.append(')')
        dfs(t)
        return ''.join(res)

class Solution(object):
    def tree2str(self, t):
        """
        :type t: TreeNode
        :rtype: str
        """
        def helper(node):
            if not node:
                return ''
            if not node.left and not node.right:
                return str(node.val)
            root = str(node.val)
            if node.left:
                root += '(' + helper(node.left) + ')'
            else:
                root += '()'
            if node.right:
                root += '(' + helper(node.right) + ')'
            return root
        return helper(t)

# level order traversal, tree to string 2
# version 1
def tree2str2(root):
    queue = [root]
    res = ""
    while queue:
        size = len(queue)
        oneLevel = ''
        for i in range(size):
            top = queue.pop(0)
            if not top:
                oneLevel += "#"
                continue
            oneLevel += str(top.val)
            queue.append(top.left)
            queue.append(top.right)
        res += oneLevel + '\n'
    print(res)
    return res

e606