心之所向便是光

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

  • 2021-08-06
  • 作者 Ender
  • 3.75K 字
  • 次阅读

题目描述：

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

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

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

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

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

示例 4：

1
2
输入：root = [1,2]
输出：[1,2]

提示：

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

链接：

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree

题目分析

  按照题目要求，我们应该是采用一种遍历方法将二叉树序列化成一个字符串进行保存，而反序列化则是将字符串重新解码构造成原来的二叉树。二叉树的遍历方法有很多种，例如前序遍历、中序遍历、后序遍历、层序遍历。观察到题目中所给的示例就是使用层序遍历进行编码的，则我也采用同样的遍历方式。
  层序遍历需要维护一个队列，保存需要遍历子树的结点。我们在序列化的时候需要考虑到反序列化的时候如何拆分序列成为单个结点，观察到结点不会超过 4 位数，且带有正负，则每个结点都可以用不多于 5 位表示，我们可以规定每 5 个位为一个结点，这是一种表示方法。而考虑到实际上大部分结点都不需要 5 位，并且 C++ 中也含有一些字符串与整型互相转化的函数，则我们可以使用 , 进行结点划分，反序列化的时候再通过 , 拆分并使用已有的转化函数应该更为方便。而空结点我们这里使用 # 进行表示。对于每个非空结点，我们都需要遍历其左右子树，这样在反序列化的时候才能够根据层序遍历顺序得到原二叉树。下面是序列化函数。整型转字符串使用的是 to_string() 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    queue<TreeNode*> q;
    string result;
    q.push(root);
    while(!q.empty()){
        TreeNode *p = q.front();
        q.pop();
        // 空结点使用 '#' 表示
        if(p == nullptr) result += "#";
        // 序列化非空结点，并将其左右子树加入待处理队列
        else{
            result += to_string(p->val);
            q.push(p->left);
            q.push(p->right);
        }
        // 每处理一个结点加上一个分隔符 ','
        result += ",";
    }
    return result;
}

  通过上面的序列化，我们得到以 , 分割的二叉树层序遍历串。进行反序列化时，我们首先要对字符串进行拆分。这里采用的是队列进行存储，使用一个字符串 str 进行记录，按字符遍历，每次遇到分隔符就拆分出一个结点。
  拆分完毕后，我们先对根结点进行判断，如果为空直接返回空指针，反之则创建根结点，作为返回结果。我们同样创建一个层序遍历的结点处理队列，同时我们使用一个布尔变量 left 来标记当前处理的是左孩子还是右孩子（这是由于进行连接的时候不能由空结点直接 new，而是需要先 new 完再进行连接，所以当前处理的是队首的左右孩子，而不是队首本身），遇到非空结点连接好之后就将其加入待处理队列中。队首的左右孩子都处理完毕之后才将队首弹出。
  这里将字符串转化为整型用到的函数是 int atoi(const char *str)，这个函数是 C 语言的函数，参数是 const char*，C 语言没有 string 类型，因此还得使用一个 const char *c_str() 函数进行转换。而 string 类型的比较函数是 compare(const string& str)。

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
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    queue<string> strs;
    string str;
    for(const char& ch : data){
        if(ch == ','){
            strs.push(str);
            str.clear();
        }
        else{
            str += ch;
        }
    }
    if(!strs.front().compare("#")) return nullptr;
    TreeNode *root = new TreeNode(atoi(strs.front().c_str()));
    strs.pop();
    queue<TreeNode*> q;
    q.push(root);
    bool left = true;
    while(!strs.empty()){
        TreeNode *now = q.front();
        string s = strs.front();
        strs.pop();
        if(left){
            if(!s.compare("#")){
                now->left = nullptr;
            }
            else{
                now->left = new TreeNode(atoi(s.c_str()));
                q.push(now->left);
            }
            left = false;
        }
        else{
            if(!s.compare("#")){
                now->right = nullptr;
            }
            else{
                now->right = new TreeNode(atoi(s.c_str()));
                q.push(now->right);
            }
            q.pop();
            left = true;
        }
    }
    return root;
}

  时间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。我们在序列化与反序列化的过程都是对二叉树进行了一次层序遍历。
  空间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。我们在序列化与反序列化的时候都需要维护一个队列，队列长度不会超过结点数，并且在反序列化时还使用了另一个队列对序列进行拆分，大小为 $n$。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-08-06