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

leetcode原题链接：leetcode-cn.com/problems/co…
难度：简单
方法：dfs

题目描述

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例

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

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

思路分析

最开始读题的理解

前序遍历 —> 中左右
对于每一个根节点而言，其左边和右边的元素需放在一个括号内。
但是在我测试样例运行的时候，发现了问题，题目的意思并非将左右两个节点放在一个括号内，而是每个节点都放在一个括号内。括号套括号。
因此按照正确的方法先将正确的没有省略的答案输出，然后再考虑如何省略

最终题意理解

判断情况即可：只有四种情况
1. 存在左节点，存在右节点
2. 存在左节点，不存在右节点 -> 需要省略
3. 不存在左节点，存在右节点
4. 不存在左节点，不存在右节点 -> 需要省略
总结：均是不存在右节点的情况，左节点可存在也可以不存在
- 针对左节点：存在时正常输出操作，不存在时必须右节点也不存在才需要省略

`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) {
  // 前序遍历：中左右
  // 左子树打印左括号，右子树打印右括号
  // 可以除去的括号：数字右边的括号，右子树为空的时候
  // 1.返回值和参数：无，每一个节点
  // 2.终止条件：节点为空的时候
  // 3.每一层的逻辑：遍历当前的左节点和右节点，并添加括号
  let ans = [];
  function dfs(node) {
    // 还需要判断是左节点还是右节点
    if(node == null) return;
    ans.push(node.val)
    if(node.right == null && node.left == null){
      dfs(node.left);
    }else {
      ans.push('(');
      dfs(node.left);
      ans.push(')');
    }
    if(node.right != null){
      ans.push('(');
      dfs(node.right);
      ans.push(')');
    }
  }
  dfs(root)
  return ans.join('')
};
复制代码