题目

类型：树

解题思路

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

所谓的不必要就是指当以某个节点 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(")");        
    }
}