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

我的错误思路

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* root) {
        string str;
        fun(root, str);
        return str;
    }

    void fun(TreeNode* root, string &s)
    {
        if(root==nullptr)
        {
            // s+=')';
            return;
        }

        s+=(root->val+'0');
        if(root->left==nullptr&&root->right)
        {
            s+="()";
        }
        else if(root->left==nullptr&&root->right==nullptr)
        {
            s+=')';
        }
        else
        {
            s+='(';
        }
        fun(root->left, s);
        if(root->left&&root->right)
        {
            s+=')';
            s+='(';
        }
        else if(root->left==nullptr&&root->right)
        {
            s+='(';
        }
        else if(root->left&&root->right==nullptr)
        {
            s+=')';
        }
        fun(root->right,s);
       
    }

};

正确思路

还是前序遍历，根、左、右
但是要求将左子树和右子树括起来
如果不先考虑去括号的话

  • 先加当前节点的值
  • 加 (
  • 递归处理左子树
  • 加 ）
  • 加 (
  • 递归处理右子树
  • 加 )

考虑去括号

  • 左右子树都为空，都去掉
  • 右为空，去掉右
  • 左为空，右不为空，不能去掉左
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string tree2str(TreeNode* root) {
        string str;
        fun(root, str);
        return str;
    }

    void fun(TreeNode* root, string &s)
    {
        if(root==nullptr)
        {
            return;
        }

        s+=to_string(root->val);
        //左边不为空，或者左边为空但是右边不为空，保留
        if(root->left||root->right)
        {
            s+='(';
            fun(root->left, s);
            s+=')';
        }
       

        if(root->right)
        {
            s+='(';
            fun(root->right,s);
            s+=')';
        }
        

    }

};

另一种写法

这种写法有个不好的点，传值返回消耗稍微有点多。

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
class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root==nullptr)
            return string();

        string str;
        str+=to_string(root->val);

        //左边不为空，或者右边不为空左边为空，都需要加括号
        if(root->left||root->right)
        {
            str+='(';
            str+=tree2str(root->left);
            str+=')';
        }

        if(root->right)
        {
            str+='(';
            str+=tree2str(root->right);
            str+=')';
        }

        return str;
    }
};