【题目】

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     

Output: "1(2(4))(3)"

Explanation: Originallay it needs to be "1(2(4)())(3()())", 
but you need to omit all the unnecessary empty parenthesis pairs. 
And it will be "1(2(4))(3)".

Example 2:

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example, 
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

下面是要编写的函数代码段:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {

    }
};

【翻译】

要求使用括号和数字的组合按照二叉树的前序遍历顺序将二叉树节点表示出来。

空的二叉树节点可以直接使用空括号()表示,在不存在歧义的地方可以省略掉空括号,例如空二叉树可以直接返回一个空字符串,在没有右节点的地方可以省略掉右结点的括号,在没有子节点的地方,可以省略掉代表左右空节点的括号。

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

注释: 与第一个例子类似,但在这里我们不能忽略掉出现的那个空括号,不然会破坏掉与二叉树中的节点一一对应的关系.

【解题思路】

一般遇到二叉树的前序遍历都会考虑使用DFS,此题也不例外,显而易见应该会用到递归的思想,每次都按照根左右的顺序进行处理,所以函数中只需要写出 第一次的处理方法,剩下的就是重复函数本身,下面是完整的c++代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* t) {
        string res;
        if(!t) return res;
        else
        {
            res.append(to_string(t -> val));
            if(!(t -> left) && !(t -> right));
            else 
            {
                res.push_back('(');
                if(!(t -> left)) res.push_back(')');
                else 
                {
                    res.append(tree2str(t -> left));
                    res.push_back(')');
                }
                if(!(t -> right));
                else 
                {
                    res.push_back('(');
                    res.append(tree2str(t -> right));
                    res.push_back(')');
                }
            }
        }
        return res;
    }
};

还想罗嗦一句的是,这个题目和之前的一道微软实习生的笔试题极为相似,具体题目记不得了,但是这是其中最简单的一道。。。微软题目还是很虐人的,桑心~~~~