根据二叉树创建字符串

题目描述：

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

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

示例 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)”

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

思路:

时间复杂度：O(n),空间复杂度O(1)

前序遍历，然后判断左孩子为空和右孩子为空两种情况特殊处理，用递归最简单了。

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func tree2str(root *TreeNode) string {
    res := ""
    if root.Left == nil && root.Right == nil{
        return strconv.Itoa(root.Val)
    }else if root.Left == nil && root.Right != nil{
        return strconv.Itoa(root.Val)+"()("+tree2str(root.Right)+")"
    }else if root.Left != nil && root.Right == nil{
        return strconv.Itoa(root.Val)+"("+tree2str(root.Left)+")"
    }
    res += strconv.Itoa(root.Val) + "("+tree2str(root.Left) + ")(" +tree2str(root.Right) + ")"
    return res
}

代码效率：

执行用时：8 ms, 在所有 Go 提交中击败了87.40%的用户
内存消耗：7.4 MB, 在所有 Go 提交中击败了59.06%的用户