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

• 审题：
  使用前序的方式，讲一个二叉树转化为一个由括号和整数组成的字符串
• 分情况讨论：

1. 右树为空，必然不加括号
2. 左树为空，在右树存在的情况下，需要加括号；右树不存在那么不需要加括号。

为什么会有这样的区分？

比如上面的树我改成这样：

那么我输出的情况是 ：1(2()(4))(3);如果不加以区分，我直接写成 1(2(4))(3)，就会导致和之前那颗树，无法区别。所以在左树为空的情况下，右树还存在的情况下，还得加上 ()。

---

我们先别考虑那么多，走一个前序遍历，我都加上括号：

class Solution {
public:
 string _tree2str(TreeNode* root,string& ret)
 {
   if(root == nullptr)
        return ret;        

        ret += to_string(root->val);
        
        ret += '(';
        _tree2str(root->left,ret);
        ret += ')';
        
         ret += '(';
        _tree2str(root->right,ret);
        ret += ')';
        return ret;
 }
    string tree2str(TreeNode* root) 
    {
        string ret;
       _tree2str(root,ret);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

看一下结果：

我简易讲一下：

前序遍历：根，左子树，右子树。

顺序：
1 -> 1(2) -> 1(2(4)) -> 1(2(4())) -> 1(2(4()())) ->1(2(4()())()) -> 1(2(4()())())(3) -> 1(2(4()())())(3()) ->1(2(4()())())(3()())

大家好好想想，现在我们的问题就是，完成去括号，也就是上面讲的左树为空，右树为空的两种情况：

class Solution {
public:
 string _tree2str(TreeNode* root,string& ret)
 {
   if(root == nullptr)
        return ret;        

        ret += to_string(root->val);
        
        if(root->left || root->right)
        {
        ret += '(';
        _tree2str(root->left,ret);
        ret += ')';
        }
        
        if(root->right)
        {
         ret += '(';
        _tree2str(root->right,ret);
        ret += ')';
         }
        return ret;
 }
    string tree2str(TreeNode* root) 
    {
        string ret;
       _tree2str(root,ret);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

这样就过了：

---