根据二叉树创建字符串

一、题目描述

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

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

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

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

二、思路分析：

阅读完题目后我们可以发现其实这就是一道考察二叉树遍历的题目，我们都知道二叉树常见的遍历方式有4种，分别是前序遍历、中序遍历、后序遍历和层序遍历，简单地回顾一下这几种遍历方式：

1、前序遍历

前序遍历又称先序遍历，遍历顺序依次为根节点->左子树->右子树，如下图：

2、中序遍历

中序遍历遍历顺序依次为左子树->根节点->右子树，如下图：

3、后序遍历

后序遍历遍历顺序依次为左子树->右子树->根节点，如下图：

4、层序遍历

层序遍历遍历顺序为按照层级依次遍历，如下图：

遍历方法

前序遍历、中序遍历和后序遍历我们可以通过递归或迭代的方式来进行遍历，层序遍历我们则可以使用队列来进行辅助遍历，读完这一题目，我们可以发现这道题的答案其实就是前序遍历的结果，我们可以使用前序遍历来简单快速地解答本题，步骤如下：

• 当前遍历的树不为空，拼接上当前节点的val
• 左子树不为空，加上括号再递归进入左子树
• 右子树不为空，如果左子树为空则需加上'()'占位，加上括号再递归进入右子树

AC代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var tree2str = function(root) {
    let res = '';
    const dfs = function(r){
        if(!r) return;
        res += r.val; //当前遍历的树不为空，拼接上当前节点的val
        if(r.left){ //左子树不为空，加上括号再递归进入左子树
            res += '(';
            dfs(r.left);
            res += ')'
        }
        if(r.right){ //右子树不为空，如果左子树为空则需加上'()'占位
            if(!r.left) res += '()';
            res += '(';  //加上括号再递归进入右子树
            dfs(r.right);
            res += ')'
        }
    }
    dfs(root);
    return res;
};