Serialization Of Tree

发表于 | 分类于

Serialization Of Tree(树的序列化和反序列化)

题目描述：

二叉树被记录文件的过程称为二叉树的序列化。通过文件来重建二叉树的过程称为二叉树的反序列化。给定一棵树的头结点head，设计一种二叉树序列化和反序列化的方案。

例子：

我们用！放在遍历结果的后面表示当前节点的结束，用#！表示当前节点为空结束。这样通过先序遍历一棵树得到的结果为：12!3!#!#!#!.

解题思路：

所以我们可以利用树的先序遍历来得到一棵树的序列化结果。在遍历每个节点后加上!,在每个根节点后面加上#!.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class serialByPre1{
public:
    string serialByPre(treeNode* root){
        string res = "";
        if (root == NULL)
            return "#!";
        res = to_string(root->val) + "!";
        res = res + serialByPre(root->left);
        res = res + serialByPre(root->right);
        return res;
    }
};

解题思路2：

对于树我们也可以使用按层遍历的方法得到其序列化的结果。使用的规则和上诉的一致，我们在节点结束后加上!,在空节点上加上#!.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class serialByLevel1{
public:
    string serialByLevel(treeNode* root){
        if (root == NULL)
            return NULL;
        string result = "";
        queue<treeNode*> q;
        stack<treeNode*> stk;//按层遍历利用两个栈来实现
        q.push(root);
        while(!q.empty()){
            cout <<  q.front()->val << endl;
            if (q.front()->left != NULL){
            		result += "#!";
                q.push(q.front()->left);
                }
            if (q.front()->right != NULL)
                q.push(q.front()->right);
            q.pop();
        }
    }
};

解题思路3

对于反序列化而言，我们首先要将拿到的字符串根据!隔开，分隔出每个节点的数值。因为原始数据是根据先序遍历得到的，所以假设在分隔后得到的字符串数组是[“12”,”3”,”#”,”#”,”#”].我们首先取出第一个字符串，开辟空间新建节点，用剩下的数据作为其左子树；取出第二个节点3生成节点，用剩下的作为左子树，发现是空节点，所以用剩下的构建右子树依旧是空节点；所以用[“#”,”#”]构建12节点的右子树。

代码如下：

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
class reconBySerialString1 {
public:
    queue<string> splitStrByDelimiter(string str) {
        queue<string> p;
        int start = 0;
        int distance = 0;
        string tmp = "";
        while (start < str.size()) {
            distance = str.substr(start, 11).find('!');
            tmp = str.substr(start, 11).substr(0, distance);
            p.push(tmp);
            start = start + distance + 1;
        }
        return p;
    }
    treeNode* reconBySerialString(queue<string> p){
        if (p.empty())
            return NULL;
        queue<treeNode*> q1;
        treeNode* head = new treeNode(stoi(p.front()));
        treeNode* result = head;
        q1.push(head);
        p.pop();
        while(!p.empty()){
            if (p.front() != "#"){
                treeNode* left = new treeNode(stoi(p.front()));
                q1.push(left);
                p.pop();
                head->left = left;
            }
            else{
                p.pop();
                head->left = NULL;
            }
            if (p.front() != "#"){
                treeNode* right = new treeNode(stoi(p.front()));
                p.pop();
                q1.push(right);
                head->right = right;
            }
            else{
                p.pop();
                head->right = NULL;
            }
            q1.pop();
            head = q1.front();
        }
        return result;
    }
};