1.题目要求给出一棵二叉树，进行序列化，然后再进行反序列化还原二叉树，而中间的序列化形式不作要求。
2.综合考虑后，我采用&val1*parentAddress1#address1&val2*parentAddress2#address2这样的格式来存储节点数据，即把一个节点的值，父节点地址和自身地址存储。因为地址从1开始递增，所以通过父节点地址的正负来区分左右节点。
3.需要注意考虑边界的情况，一开始我使用了0来作为根节点的地址，但是0没有正负之分，所以不能区分左右孩子，于是改为1作为根节点。
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
1
/ \
2 3
/ \
4 5
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.
Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.
AC代码：
[c language=”++”]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
string int2str(int a)
{
bool sign = true;
if (a < 0)
{//注意负数情况
sign = false;
a = -a;
}
if (a == 0) return "0";
string result = "";
while (a != 0)
{
char c = a % 10 + ‘0’;
result = c + result;
a /= 10;
}
if (!sign) result = "-" + result;
return result;
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
int address = 1;//根节点地址需要为1，因为需要通过正负的父地址来判断左右子树
queue<pair<TreeNode*, int>> q;//first为节点，second为地址
vector<pair<int, pair<int, int>>> arr(0);//first为val,second.first为父亲地址，second.second为自己地址
int count1 = 0;
int count2 = 0;
if (root != NULL)
{//根节点的父节点地址为1
arr.push_back({ root->val, { INT_MAX, address } });
q.push({ root, address });
address++;
count1++;
}
while (!q.empty())
{
//广度遍历树，记录每个节点的值，父节点地址，地址
for (int i = 0; i < count1; i++)
{
pair<TreeNode*, int> head = q.front();
q.pop();
int parentAdd = head.second;//父亲节点的地址
TreeNode* tmp = head.first;
if (tmp->left != NULL)
{//左儿子不为空
arr.push_back({ tmp->left->val, { parentAdd, address } });
q.push({ tmp->left, address });
address++;
count2++;
}
if (tmp->right != NULL)
{//父节点为负数，表示是右儿子
arr.push_back({ tmp->right->val, { -parentAdd, address } });
q.push({ tmp->right, address });
address++;
count2++;
}
}
count1 = count2;
count2 = 0;
}
string result = "";//最终结果
for (int i = 0; i < arr.size(); i++)
{//格式为&val*parentAddress#address
result += "&" + int2str(arr[i].first) + "*" + int2str(arr[i].second.first) + "#" + int2str(arr[i].second.second);
}
return result;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
map<int, TreeNode*> m;
vector<pair<int, pair<int, int>>> arr(0);//还原成数组
int process = -1;
bool sign = true;
int val=-1, parentAdd=INT_MAX, add=0;
for (int i = 0; i < data.size(); i++)
{
if (process == 0)
{//此时检测的是val
if (data[i] == ‘-‘)
sign = false;
else if (data[i] == ‘*’)
{
if (!sign) val = -val;
process++;
sign = true;
}
else
val = val * 10 + data[i] – ‘0’;
}
else if (process == 1)
{//此时检测的是parentAdd
if (data[i] == ‘-‘)
sign = false;
else if (data[i] == ‘#’)
{
if (!sign) parentAdd = -parentAdd;
process++;
sign = true;
}
else
parentAdd = parentAdd * 10 + data[i] – ‘0’;
}
else if (process == 2)
{//此时检测的是add
if (data[i] == ‘-‘)
sign = false;
else if (data[i] == ‘&’)
process = -1;
else
add = add * 10 + data[i] – ‘0’;
}
//检测是否到了下一个开始
if (process == -1 && data[i] == ‘&’)
{
if (i != 0)
{//如果i==0，初始值，不需要压入，i>0才需要
if (!sign) add = -add;
arr.push_back({ val, { parentAdd, add } });
}
sign = true;//初始化符号为正号
val = 0;
parentAdd = 0;
add = 0;
process++;
}
}
//补充最后一个值
if (data != "")
{
if (!sign) add = -add;
arr.push_back({ val, { parentAdd, add } });
}
for (int i = 0; i < arr.size(); i++)
{//把arr通过map还原成树
int parentAdd = arr[i].second.first;
int add = arr[i].second.second;
int val = arr[i].first;
m[add] = new TreeNode(val);
if (parentAdd != INT_MAX)
{
if (parentAdd < 0)
m[-parentAdd]->right = m[add];
else
m[parentAdd]->left = m[add];
}
}
if (data!="")
return m[1];
else return NULL;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
[/c]