题目描述

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

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

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

题解

就是将一棵树二叉树用一个字符串表示，根据这个字符串能重建二叉树即可。

序列化的规则没有限制，只要反序列化时根据序列化时的规则能够重建就行。

BFS 遍历

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
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        string ans = "";
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            if (!node) ans += "null,";
            else ans += to_string(node->val) + ",";
            if (node) q.push(node->left);
            if (node) q.push(node->right);
        }
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "") return nullptr;
        queue<string> dataQ;
        string val;
        for (char c : data) {
            if (c == ',') dataQ.push(move(val));
            else val += c;
        }
        auto getTreeNode = [](auto&& val) -> TreeNode* {
            return val == "null" ? nullptr : new TreeNode(stoi(val));
        };
        queue<TreeNode*> nodeQ;
        nodeQ.push(getTreeNode(dataQ.front())); dataQ.pop();
        TreeNode* root = nodeQ.front();
        while (!dataQ.empty()) {
            TreeNode* node = nodeQ.front(); nodeQ.pop();
            node->left = getTreeNode(dataQ.front()); dataQ.pop();
            node->right = getTreeNode(dataQ.front()); dataQ.pop();
            if (node->left) nodeQ.push(node->left);
            if (node->right) nodeQ.push(node->right);
        }
        // 也可以用 vector<string> dataArray 代替 queue<string> dataQ
        // TreeNode* root = dataArray[0];
        // for (int i = 1; i < dataArray.size() - 1; i += 2) {
        //     TreeNode* node = q.front(); q.pop();
        //     node->left = getTreeNode(dataArray[i]);
        //     node->right = getTreeNode(dataArray[i + 1]);
        //     if (node->left) q.push(node->left);
        //     if (node->right) q.push(node->right);
        // }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

时间复杂度 O(N)，空间复杂度 O(N)

DFS 遍历

下面使用先序遍历，其他顺序遍历也可以，序列化和反序列化的顺序一致即可。

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
class Codec {
    void serializeDfs(TreeNode* root, string& ans) {
        if (!root) {
            ans += "null,";
            return;
        }
        ans += to_string(root->val) + ",";
        serializeDfs(root->left, ans);
        serializeDfs(root->right, ans);
    }
    TreeNode* deserializeDfs(queue<string>& dataArray) {
        if (dataArray.front() == "null") {
            dataArray.pop();
            return nullptr;
        }
        TreeNode* node = new TreeNode(stoi(dataArray.front()));
        dataArray.pop();
        node->left = deserializeDfs(dataArray);
        node->right = deserializeDfs(dataArray);
        return node;
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        serializeDfs(root, ans);
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> dataArray;
        string val;
        for (char c : data) {
            if (c == ',') dataArray.push(move(val));
            else val += c;
        }
        return deserializeDfs(dataArray);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

时间复杂度 O(N)，空间复杂度 O(N)