Serialize and Deserialize BST

第三天。

今天的题是[https://leetcode.com/problems/serialize-and-deserialize-bst/](Serialize and Deserialize BST):

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

这个题目需要我们实现两个函数，一个对BST进行序列化，一个对BST进行反序列化。总的来说对算法要求不高（时间上），但是要求序列化出来的字符串尽量小。

首先要解决两个问题：

如何序列化一个正常节点
如何序列化一个NULL节点

这里面我们采取这样一个方法，一个正常的节点由以下结构组成：

1
struct {
2
  char flag = 'Y';
3
  union INT {
4
    int iv;
5
    char cv[4];
6
  };
7
};

其中flag来标识，这是一个正常的节点，而INT则是存放节点的值，通过union,我们可以方便的将int转换为char数组。

一个NULL的节点当然也可以通过上面的结构组成，但是对于NULL节点来说，后面的INT其实没有必要，所以我们直接通过字符N来标识NULL节点。

因此，我们的实现如下：

1
class Codec {
2
public:
3

4
    union INT {
5
        int iv;
6
        unsigned char cv[4];
7
    };
8
    // Encodes a tree to a single string.
9
    string serialize(TreeNode* root) {
10
        string str;
11
        serialize(root, str);
12
        return str;
13
    }
14

15
    void serialize(TreeNode *root, string &str) {
44 collapsed lines
16
        if (root == NULL) {
17

18
            str.push_back('N');
19
            return;
20
        }
21

22
        INT val;
23
        val.iv = root->val;
24

25
        str.push_back('Y');
26
        for(int i = 0;i < 4;i++) {
27
            str.push_back(val.cv[i]);
28
        }
29

30

31
        serialize(root->left, str);
32
        serialize(root->right, str);
33
    }
34

35

36
    // Decodes your encoded data to tree.
37
    TreeNode* deserialize(string data) {
38
        int index = 0;
39
        return deserialize(data, index);
40
    }
41

42
    TreeNode *deserialize(string &data, int &index) {
43
        if (index >= data.size() || data[index] == 'N') {
44
            index += 1;
45
            return nullptr;
46
        }
47
        index += 1;
48
        INT val;
49
        for(int i = 0;i < 4;i++) val.cv[i] = (unsigned char)data[index + i];
50

51

52
        index += 4;
53
        TreeNode *root = new TreeNode(val.iv);
54
        root->left = deserialize(data, index);
55
        root->right = deserialize(data, index);
56

57
        return root;
58
    }
59
};