二叉树的序列化和反序列化
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
【LintCode 二叉树的序列化和反序列化 题解】如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
注意事项 There is no limit of how you deserialize or serialize a binary tree, LintCode will take your output of
serialize as the input of deserialize, it won't check the result of serialize.您在真实的面试中是否遇到过这个题？Yes 样例 给出一个测试数据样例， 二叉树
{3,9,20,#,#,15,7}，表示如下的树结构：3
/ \
920
/\
157
我们的数据是进行BFS遍历得到的。当你测试结果wrong answer时，你可以作为输入调试你的代码。
你可以采用其他的方法进行序列化和反序列化。
解题思想：
本题的主要思想是进行层次遍历。
1.首先对二叉树进行层次遍历，对于NULL的节点用字符#表示，每一个节点直接使用，进行分割
2.所以序列化后的二叉树输出的字符串data应该形如：string datahttps://www.it610.com/article/= "https://www.it610.com/article/1,2,3,#,#,4,5,#,#,6,7";
3.反序列化的思想同样是这样，首先将string分割成一个个的节点集合vector tree，对于非NULL节点插入到一个execute队列中，插入到队列同时删除tree中对应节点。
4.每次处理execute队列的队首元素，从tree中取出前两个元素分别作为左右子节点，tree中删除前两个元素，对于不是#的元素，将其插入到execute队列中；对于是#的元素不操作。
5.重复第4步，直到execute队列为空。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
*int val;
*TreeNode *left, *right;
*TreeNode(int val) {
*this->val = val;
*this->left = this->right = NULL;
*}
* }
*/
class Solution {
public:
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
string serialize(TreeNode *root) {//序列化
// write your code here
string datahttps://www.it610.com/article/= "";
if (root == NULL)
return data;
vector queue;
queue.push_back(root);
// 将二叉树的个节点按照从上到下、从左到有的存储在queue中
for (int i = 0;
ileft);
queue.push_back(q->right);
}
for (int i = 0;
ival);
s = t;
data += (s + ",");
}
else
{
data += "#,";
}
} return data;
}TreeNode *deserialize(string data) {//反序列化
// write your code here
if (data =https://www.it610.com/article/="")
return NULL;
vector tree = split(data, ",");
//分割得到每一个节点
queue execute;
//待插入子树的节点队列 TreeNode * root = (TreeNode*)malloc(sizeof(TreeNode));
//创建根节点
root->left = root->right = NULL;
root->val = atoi(tree[0].c_str());
tree.erase(tree.begin());
TreeNode* p = root;
execute.push(p);
while (execute.size() != 0)
{
if (tree.size()<2)
break;
TreeNode* cur = execute.front();
execute.pop();
if (tree[0] != "#")//处理左子树
{
TreeNode* tem = (TreeNode*)malloc(sizeof(TreeNode));
tem->val = atoi(tree[0].c_str());
tem->left = tem->right = NULL;
cur->left = tem;
execute.push(tem);
//左节点不是NULL，所以需要插入到队列中，准备插入其自己的左右子节点
tree.erase(tree.begin());
//删除tree中该节点表示该节点已经处理过了}
else
{
tree.erase(tree.begin());
//如果cur的左节点是NULL，直接删除Tree中的该节点表示已经处理就好了。
}if (tree[0] != "#")//处理右子树
{
TreeNode* tem = (TreeNode*)malloc(sizeof(TreeNode));
tem->val = atoi(tree[0].c_str());
tem->left = tem->right = NULL;
cur->right = tem;
execute.push(tem);
tree.erase(tree.begin());
}
else
{
tree.erase(tree.begin());
} } return root;
}
};
