297. 二叉树的序列化与反序列化#

题目#

1
序列化是将一个数据结构或者对象转换为连续的比特位的操作，
2

3
进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，
4

5
采取相反方式重构得到原数据。
6

7
请设计一个算法来实现二叉树的序列化与反序列化。
8

9
这里不限定你的序列 / 反序列化算法执行逻辑，
10

11
你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
12

13
提示: 输入输出格式与 LeetCode 目前使用的方式一致，
14

15
详情请参阅 LeetCode 序列化二叉树的格式。
16

17
你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
18

19
示例 1：
20

21
输入：root = [1,2,3,null,null,4,5]
22
输出：[1,2,3,null,null,4,5]
23

24
示例 2：
25

26
输入：root = []
27
输出：[]
28

29
示例 3：
30

31
输入：root = [1]
32
输出：[1]
33

34
示例 4：
35

36
输入：root = [1,2]
37
输出：[1,2]
38

39

40
提示：
41

42
树中结点数在范围 [0, 10^4] 内
43
-1000 <= Node.val <= 1000

题目思路#

本质上还是 DFS 与 BFS 的题目，但此题难度较大，所以花费时间较长；
DFS 有前序、后序两种递归形式，后序遍历因为时间限制暂时没有写；而中序遍历由于无法确定根节点，所以无法形成递归形式。

题目代码#

代码块#

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
 * };
9
 */
10
class Codec {
11
public:
12
    /* void predfs(TreeNode* root, string& data)
13
    {
14
        if(root == nullptr) data += "null,";
15
        else
16
        {
17
            data += to_string(root -> val) + ",";
18
            predfs(root -> left, data);
19
            predfs(root -> right, data);
20
        }
21
    }
22

23
    string serialize(TreeNode* root)
24
    {
25
        string data;
26
        predfs(root, data);
27
        return data;
28
    }
29

30
    TreeNode* rdfs(list<string>& str)
31
    {
32
        if (str.front() == "null")
33
        {
34
            str.erase(str.begin());
35
            return nullptr;
36
        }
37
        TreeNode* root = new TreeNode(stoi(str.front()));
38
        str.erase(str.begin());
39
        root -> left = rdfs(str);
40
        root -> right = rdfs(str);
41
        return root;
42
    }
43

44
    TreeNode* deserialize(string data)
45
    {
46
        list<string> str;
47
        string s;
48
        for (auto& ch : data)
49
        {
50
            if (ch == ',')
51
            {
52
                str.push_back(s);
53
                s.clear();
54
            }
55
            else s.push_back(ch);
56
        }
57
        if (s.empty() != 0)
58
        {
59
            str.push_back(s);
60
            s.clear();
61
        }
62
        return rdfs(str);
63
    } */
64
    string serialize(TreeNode* root) {
65
        string ans;
66
        queue<TreeNode* > q;
67
        if(root == nullptr) return ans;
68
        else q.push(root);
69
        while(!q.empty())
70
        {
71
            int n = q.size();
72
            for(int i = 0; i < n; ++i){
73
                auto node = q.front();
74
                q.pop();
75
                if(node == nullptr) ans += "null,";
76
                else
77
                {
78
                    ans += to_string(node->val) + ",";
79
                    q.push(node->left);
80
                    q.push(node->right);
81
                }
82
            }
83
        }
84
        return ans;
85
    }
86
    TreeNode* deserialize(string data) {
87
        if(data.empty()) return NULL;
88
        vector<TreeNode* > ans;
89
        int k = 0;
90
        int n = data.size();
91
        while(k < n)
92
        {
93
            string tmp;
94
            while(data[k] != ',')
95
            {
96
                tmp += data[k];
97
                k++;
98
            }
99
            if(tmp == "null") ans.push_back(NULL);
100
            else ans.push_back(new TreeNode(stoi(tmp)));
101
            tmp.clear();
102
            k++;
103
        }
104
        int pos = 1;
105
        for(int i = 0; i < ans.size(); i++)
106
        {
107
            if(ans[i] == NULL) continue;
108
            ans[i] -> left = ans[pos++];
109
            ans[i] -> right = ans[pos++];
110
        }
111
        return ans[0];
112
    }
113
};
114
// Your Codec object will be instantiated and called as such:
115
// Codec ser, deser;
116
// TreeNode* ans = deser.deserialize(ser.serialize(root));

复杂度#

时间复杂度：O(n)
空间复杂度：O(n)