剑指offer37 序列化二叉树

发表于 | 分类于 |
字数统计: 537 | 阅读时长 ≈ 2

链接: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/

题意

请实现两个函数，分别用来序列化和反序列化二叉树。

解法

代码实现了将二叉树的结构转化为以字符串形式存储的数组
以及将以字符串形式存储的二叉树还原成二叉树的原始结构
借助LeetCode使用的层次遍历的形式进行存储
代码写的比较长，一开始是严格按照LeetCode标准进行存储的
后来进行一些改进，会把每一层中最后的空节点保留
但是这个保留其实是可以接受的，因为解码编码都是自己进行实现的
细节见代码
主要用到了一个队列 用一个数组保存当前层的所有节点

代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "[]";
        queue<TreeNode*> q;
        q.push(root);
        string ans = "[";
        while(q.size()) {
            int flag = 0;
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode* temp = q.front();
                q.pop();
                if (!temp) {
                     ans += "null,";
                }
                else {
                    ans += to_string(temp -> val) + ",";
                    if (temp -> left || temp -> right) {
                        flag = 1;
                    }
                    q.push(temp -> left);
                    q.push(temp -> right);
                }
            }
            if (!flag) break; // 如果当前层已经是最后一层 直接退出
        }
        ans.back() = ']';
        // cout << "serialize " << ans << endl;
        return ans;
    } 
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "[]") return nullptr;
        vector<int> seq;
        int val = 0, flag = 1;
        for (int i = 1; i < data.size(); i++) {
            if (data[i] == ',' || data[i] == ']') {
                seq.push_back(flag * val);
                val = 0;
                flag = 1;
            }
            else if (data[i] == 'n') {
                while(i < data.size() && data[i] != ',') {
                    i++;
                }
                seq.push_back(-100);
            }
            else if (data[i] == '-') {
                flag = -1;
            }
            else {
                val = val * 10 + data[i] - '0';
            }
        }
        int index = 0;
        TreeNode* root = new TreeNode(seq[index++]);
        queue<TreeNode*> q;
        q.push(root);
        while(q.size() && index < seq.size()) {
            int n = q.size();
            for (int i = 0; i < n && index < seq.size(); i++) {
                TreeNode* now = q.front();
                q.pop();
                if (seq[index] != -100) {
                    now -> left = new TreeNode(seq[index++]);
                    q.push(now -> left);
                }
                else {
                    index++;
                }
                if (index == seq.size()) break;
                if (seq[index] != -100) {
                    now -> right = new TreeNode(seq[index++]);
                    q.push(now -> right);
                }
                else {
                    index++;
                }
            }
        }
        return root;
    }
};