Description
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 tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself. Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Solution
这是一道设计题,其实就是设计以encoding算法,使得效率尽可能高, 设计思路
- 这里我们可以利用到int设计的例子,用1个bit表示该节点是否为nullptr,还是内存中存在该节点,如果该节点确实存在该节点,我们在用一个int大小记录其实际的值.
- 想法很美好,但是由于机器需要对齐的原则,(LeetCode上是4个字节的对齐原则),所以我们需要用1个int记录其”flag”状态,虽然优点浪费,但是相比较之前的将数字转成string对于大数来说更加耗费内存,
以下是我post在discuss中的内容
This idea is come up with by my roommate @HelloKenLee, and beat 92%
How to serialize the tree
This idea is similar to representation of INT,we use a sign bit,and data bits.
- So,we can use 1 int to represent this data whether is NULL or TreeNode,if it’s a TreeNode we use one more bit to represent its num(int).
- We can stored each TreeNode base on level traversal,and we can use string constructor(const char ptr,u_size n) to conver int to string like this encode += string(reinterpret_cast<char>(&flag),4);
- I have no idea to use 1 bit to represent the “flag” bit due to principle of 4 byte alignment.If you figure out this,please let me know!
How to deserialize the data
It’s not difficult to deserialize the data while you serialize the tree successfully :),But firstly , maybe you should use cast to conver string to char *,like this
char str = const_cast<char>(data.c_str());
int* pointer = reinterpret_cast<int*> (str);
Behind this cast is a simple BFS operation
Detailed implementation you can see the following code
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
queue<TreeNode*> que;
string encode;
int flag;
que.push(root);
while(!que.empty()){
TreeNode *tmp = que.front();
que.pop();
flag = tmp == nullptr ? 0 : 1;
encode += string(reinterpret_cast<char*>(&flag),4);
if(flag){
int num = tmp->val;
encode += string(reinterpret_cast<char*>(&num),4);
que.push(tmp->left);
que.push(tmp->right);
}
}
return encode;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
char *str = const_cast<char*>(data.c_str());
int* pointer = reinterpret_cast<int*> (str);
if(*pointer++==0){//root == nullptr
return nullptr;
}
TreeNode *root = new TreeNode(*pointer++);
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode *tmp = que.front();
que.pop();
if(tmp == nullptr)
continue;
if(tmp->left = *pointer++ == 0 ? nullptr : new TreeNode(*pointer++))//left subtree
que.push(tmp->left);
if(tmp->right = *pointer++ == 0 ? nullptr : new TreeNode(*pointer++))//right subtree
que.push(tmp->right);
}
return root;
}
};