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

题目描述

这是 LeetCode 上的 606. 根据二叉树创建字符串 ，难度为 简单。

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例 1:

输入: 二叉树: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

输出: "1(2(4))(3)"

解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。

示例 2:

输入: 二叉树: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

输出: "1(2()(4))(3)"

解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

---

递归

生成字符串的规则其实就是在「前序遍历」输出节点值的同时，在每颗子树的左右添加一对 ()（根节点除外），同时需要忽略掉一些不必要的 () 。

所谓的不必要就是指当以某个节点 $x$ 为根时，其只「有左子树」而「没有右子树」时，右子树的 () 可被忽略，或者「左右子树都没有」时，两者的 () 可被忽略。

或者反过来说，如果对于每个非空节点才添加 () 的话，那么当「有右子树」同时「没有左子树」时，左子树的 () 不能被忽略，需要额外添加，从而确保生成出来的字符串能够与「有左子树」同时「没有右子树」的情况区分开来，而不会产生二义性。

代码：

class Solution {
    StringBuilder sb = new StringBuilder();
    public String tree2str(TreeNode root) {
        dfs(root);
        return sb.substring(1, sb.length() - 1);
    }
    void dfs(TreeNode root) {
        sb.append("(");
        sb.append(root.val);
        if (root.left != null) dfs(root.left);
        else if (root.right != null) sb.append("()");
        if (root.right != null) dfs(root.right);
        sb.append(")");        
    }
}

• 时间复杂度：令点数为 $n$，边数为 $m$。整体复杂度为 $O(n + m)$
• 空间复杂度：$O(n)$

---

迭代（非递归）

自然也能使用「迭代（非递归）」来做，使用栈来模拟上述递归过程。

由于当以某个节点 $x$ 为根节点时，其需要在 开始 前序遍历当前子树时添加 (，在 结束 前序遍历时添加 )，因此某个节点需要出入队两次。

同时区分是首次出队（开始前序遍历）还是二次出队（结束前序遍历），这需要使用一个 set 来做记录，其余逻辑与「递归」做法类似。

代码：

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Set<TreeNode> vis = new HashSet<>();
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            TreeNode t = d.pollLast();
            if (vis.contains(t)) {
                sb.append(")");
            } else {
                d.addLast(t);
                sb.append("(");
                sb.append(t.val);
                if (t.right != null) d.addLast(t.right);
                if (t.left != null) d.addLast(t.left);
                else if (t.right != null) sb.append("()");
                vis.add(t);
            }
        }
        return sb.substring(1, sb.length() - 1);
    }
}

• 时间复杂度：令点数为 $n$，边数为 $m$。整体复杂度为 $O(n + m)$
• 空间复杂度：$O(n)$

---

迭代（通用非递归）

上述的「迭代（非递归）」解法，我们还是需要针对题目再做简单分析。

而利用通用的「递归」转「非递归」技巧，我们可以直接对「递归」解法进行改写，同时利用通用非递归过程中的 loc 可以帮助我们省掉用作区分是否首次出队的 set 结构。

需要特别说明的是：由于现代编译器已经做了很多关于递归的优化，现在这种技巧已经无须掌握。

代码：

class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{0, root});
        while (!d.isEmpty()) {
            Object[] poll = d.pollLast();
            int loc = (Integer)poll[0]; TreeNode t = (TreeNode)poll[1];
            if (loc == 0) {
                sb.append("(");
                sb.append(t.val);
                d.addLast(new Object[]{1, t});
            } else if (loc == 1) {
                d.addLast(new Object[]{2, t});
                if (t.right != null) d.addLast(new Object[]{0, t.right});
                if (t.left != null) d.addLast(new Object[]{0, t.left});
                else if (t.right != null) sb.append("()");
            } else if (loc == 2) {
                sb.append(")");
            }
        }
        return sb.substring(1, sb.length() - 1);
    }
}

• 时间复杂度：令点数为 $n$，边数为 $m$。整体复杂度为 $O(n + m)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.606 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。