JZ61 序列化二叉树

本文最后更新于：2022年4月9日 中午

image-20211010154125674

Solution

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
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    char* Serialize(TreeNode *root) {    
        string s = "";
        s = preSerialize(root);
        char *res = new char[s.size()];
        for (int i = 0; i < s.size(); ++i) {
            res[i] = s[i];
        }
        return res;
    }
    TreeNode* Deserialize(char *str) {
        return preDeserialize(str);
    }
    
private:
    string preSerialize(TreeNode *root) {
        if (root == nullptr) 
            return "#,";
        string s = "";
        s = to_string(root->val) + ',';
        
        s += preSerialize(root->left);
        s += preSerialize(root->right);
        return s;
    }
    
    TreeNode* preDeserialize(char*& s) {
        if (*s == '#') {
            s++;
            return nullptr;
        }
        int num = 0;
        while (*s != ',') {
            num = num * 10 + *s - '0';
            s++;
        }
        TreeNode* root = new TreeNode(num);
        
        root->left = preDeserialize(++s);
        root->right = preDeserialize(++s);
        return root;
    }
};
  • 层次遍历
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
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        string str;
        while(q.size()){
            TreeNode* t=q.front();
            q.pop();
            if(t)str+=to_string(t->val)+" ";
            else{
                str+="* ";
                continue;
            }
            q.push(t->left);
            q.push(t->right);
        }
        //cout<<str;
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss<<data;
        string str1,str2;
        ss>>str1;
        if(str1=="*")return NULL;
        TreeNode* root=new TreeNode(stoi(str1));
        queue<TreeNode*> q;
        q.push(root);
        while(ss>>str1){
            if(!(ss>>str2))break;
            TreeNode* t=q.front();
            q.pop();
            if(str1=="*")t->left=NULL;
            else{
                TreeNode* node=new TreeNode(stoi(str1));
                t->left=node;
                q.push(node);
            }
            if(str2=="*")t->right=NULL;
            else{
                TreeNode* node=new TreeNode(stoi(str2));
                t->right=node;
                q.push(node);
            }
        }
        return root;
    }
};