剑指 Offer 37. 序列化二叉树 - 力扣（LeetCode）
题目大意：
将一棵二叉树序列化成字符串，然后通过该字符串可以重新构造出二叉树
思路：
-
看到将二叉树转化成字符串，首先想到的是可以通过将二叉树转换成先序遍历和中序遍历，然后通过先序遍历和中序遍历重新构造二叉树。然而这个方法失败了，因为存在节点值相同的节点，这样就无法在中序序列里面找到先序遍历对应的值。
-
因此我们可以考虑使用BFS，但是使用BFS的话，要如何反序列化呢？
-
我们知道，当一颗二叉树是满二叉树时，如果节点索引是从0开始编号的话，对于索引位i的节点，他的左孩子的索引是2*i+1，右孩子的索引是2*i+2.因此我们可以考虑通过填充null将二叉树改造成满二叉树。然而这种想法是无法实现的，当二叉树退化成一条链的时候，想要将其扩充成满二叉树，时间和空间复杂度都会爆炸。
-
其实上面的结论可以推广到不是满二叉树的情况。首先，左孩子和右孩子的索引肯定是相差一。然后我们可以这样思考：对于索引为i的节点，我们设该节点之前存在m个null节点。因此在i之前存在(i-m+1)个非null节点，除根节点外，每增加一个非null节点，该节点首先会取代一个null节点，然后会增加两个null子节点。因此每增加一个非null节点需要用掉2个索引。而root节点会用掉3个索引。综上，节点i之前的节点会用掉3+(i-m+1-2)*2=2*(i-m)+1,因此i的左孩子的索引为（i-m)*2+1,右孩子为（i-m)*2+2.
因此我们可以递归构建二叉树：
点击查看代码
/**
* 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:
vector<int> v;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
queue<TreeNode*> q;
int cnt=0;
q.push(root);
string s="";
while (!q.empty())
{
TreeNode* temp=q.front();
q.pop();
if (temp){
s.append(" "+to_string(temp->val));
q.push(temp->left);
q.push(temp->right);
v.push_back(cnt);
}else{
s.append(" -223221");
cnt++;
v.push_back(cnt);
}
}
return s;
}
TreeNode* dfs(int k,vector<int>& data){
//cout<<k<<" ";
if (data[k]==-223221)
{
return NULL;
}else{
TreeNode* root=new TreeNode(data[k]);
root->left=dfs(2*(k-v[k])+1,data);
root->right=dfs(2*(k-v[k])+2,data);
return root;
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
//cout<<data.length();
vector<int> arr;
int pre=0;
int i=1;
data.push_back(' ');
while (i<data.length())
{
if (data[i]==' '){
arr.push_back(stoi(string(data,pre+1,i-pre-1)));
pre=i;
}
i++;
}
TreeNode* root=dfs(0,arr);
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
事实上，如果使用BFS反序列化，就不需要知道孩子节点的索引，因为只有非null节点才有孩子，因此可以使用一个指针指向第二个节点（因为第一个节点要作为root），然后每次遇到非空节点，都将指针指向的节点挂到该非空节点之下，然后指针右移。
点击查看代码
/**
* 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:
//vector<int> v;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
queue<TreeNode*> q;
//int cnt=0;
q.push(root);
string s="";
while (!q.empty())
{
TreeNode* temp=q.front();
q.pop();
if (temp){
s.append(" "+to_string(temp->val));
q.push(temp->left);
q.push(temp->right);
//v.push_back(cnt);
}else{
s.append(" #");
//cnt++;
//v.push_back(cnt);
}
}
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
//cout<<data.length();
vector<TreeNode*> arr;
int pre=0;
int i=1;
data.push_back(' ');
while (i<data.length())
{
if (data[i]==' '){
string tt=string(data,pre+1,i-pre-1);
if (tt[0]=='#')
arr.push_back(NULL);
else
arr.push_back(new TreeNode(stoi(tt)));
pre=i;
}
i++;
}
if (arr.size()==0 or arr[0]==NULL)
{
return NULL;
}
int pos=1;
for (int i=0;i<arr.size();i++)
{
if (arr[i]==NULL)
continue;
arr[i]->left=arr[pos++];
arr[i]->right=arr[pos++];
}
return arr[0];
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));