LeetCode Algorithm 606. 根据二叉树创建字符串

606. 根据二叉树创建字符串

Ideas

把我珍藏多年的二叉树前序遍历代码模板呈上来：

def preorderTraversalLoop(node): if not node: return stack = [node] # list 模拟 stack while stack: tmp = stack.pop() print(tmp.value, end=' ') if tmp.right: stack.append(tmp.right) if tmp.left: stack.append(tmp.left) 

这是通过列表来模拟栈进行非递归前序遍历的代码，但是这道题跟前序遍历还有所不同，还需要输出额外的括号。

我们来分析一下，有以下4种情况：

1. 当前节点有两个孩子，需要在两个孩子的结果外都加上一层括号
2. 当前节点没有孩子，不需要在节点后面增加任何括号
3. 当前节点只有左孩子没有右孩子，那么只需要给左孩子的结果外加上一层括号
4. 当前节点只有右孩子没有左孩子，此时在输出右孩子之前需要先输出一对空括号，表示左孩子为空，右孩子的结果外加上一层括号

对于某一个节点的括号输出情况，我们需要在节点值输出之前打印一个"("，然后在这颗子树输出完之后再输出一个")"。

也就是说，我们在第一次到达某个节点时输出左括号和节点值，然后将节点压入栈中，遍历完了子树之后，再回到这个节点时，输出一个右括号。

为了所有节点统一处理，我们在根节点之前也要输出一个括号，保证统一，最后再把最外层的括号去掉就可以了。

Code Python

class Solution: def tree2str(self, root: Optional[TreeNode]) -> str: if not root: return '' stack = [root] visit, ans = set(), "" while stack: item = stack[-1] if item in visit: stack.pop() ans += ')' else: visit.add(item) ans += f"({item.val}" if item.left is None and item.right is not None: ans += "()" if item.right: stack.append(item.right) if item.left: stack.append(item.left) return ans[1:-1]