606. Construct String from Binary Tree

Construct String from Binary Tree - LeetCodeLeetCode

二叉树遍历，第一反应递归。

本身 not t 这个跳出条件很明显，需要多考虑的是：

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.

所以search左子树之后，要先确认是否符合「左子树空，右子树非空」的情况，符合的话直接添加()占位，再search右子树。而右子树不需要进行这个确认，因为它空也不需要占位。

# 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 ""
        res = str(t.val)
        if t.left: res+="(" + self.tree2str(t.left) + ")"
        if not t.left and t.right: res+="()"    
        if t.right: res+="(" + self.tree2str(t.right) + ")"
        return res

要省空间的话可以用stack来写，O(n)的空间复杂度。

class Solution:
    def tree2str(self, t: TreeNode) -> str:
        if not t:
            return ""
        res = ""
        stack = [t]
        visited = []
        while stack:
            cur = stack[-1]
            if cur in visited:
                stack.pop()
                res += ")"
            else:
                visited.append(cur)
                res += "("+str(cur.val)
                if (not cur.left) and cur.right: res += "()"
                if cur.right: stack.append(cur.right)
                if cur.left: stack.append(cur.left)
        return res[1:len(res)-1]

反过来做的这道题要更麻烦点，虽然也用stack：536. Construct Binary Tree from String