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)”
解释: 和第一个示例相似，除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

�除了根节点，遍历左子树前需要加左括号，遍历左子树后需要加右括号，遍历右子树前需要加左括号，遍历右子树后需要加有括号：

String result = "";
public String tree2str(TreeNode root) {
    preOrder(root);
    return result;
}
public void preOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    result += node.val;
    // 遍历左子树前加左括号
    result += "(";
    preOrder(node.left);
    // 遍历左子树后加右括号
    result += ")";
    // 遍历右子树前加左括号
    result += "(";
    preOrder(node.right);
    // 遍历右子树后加右括号
    result += ")";
}

输入: 二叉树: [1,2,3,4]
输出：1(2(4()())())(3()())
输入: 二叉树: [1,2,3,null,4]
输出：1(2()(4()()))(3()())
测试发现，所有的空节点都加上了一对空括号，但是题意还需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
那什么样的空括号对不影响字符串与原始二叉树之间的一对一映射关系呢？
从题目示例中可以知：
1）若节点没有子节点，那么节点的两个子节点对应的空括号对可以省略
2）若节点有子节点，且左子节点和右子节点都不为空，那么不会有空括号对
3）若节点有子节点，且左子节点不为空，右子节点为空，那么右子节点的空括号对可以省略
4）若节点有子节点，且左子节点为空，右子节点不为空，那么左子节点的空括号对不可以省略

String result = "";
public String tree2str(TreeNode root) {
    preOrder(root);
    return result;
}
public void preOrder(TreeNode node) {
    if (node == null) {
        return;
    }
    result += node.val;
    if (node.left == null && node.right == null) {
       // 无子节点，无需继续遍历 
       return;
    }
    if (node.right == null) {
        // 若右子树为空，则只需要加左子树的括号即可
        // 遍历左子树前加左括号
        result += "(";
        preOrder(node.left);
        // 遍历左子树后加右括号
        result += ")";
        preOrder(node.right);
    } else {
        // 遍历左子树前加左括号
        result += "(";
        preOrder(node.left);
        // 遍历左子树后加右括号
        result += ")";
        // 遍历右子树前加左括号
        result += "(";
        preOrder(node.right);
        // 遍历右子树后加右括号
        result += ")";
    }
}