二叉树的序列化与反序列化
序列化后在char类型中的保存
序列化时因为char的长度为256，这里两道题都将一个value通过%100拆分成两部分通过两个char保存，反序列化时再从char还原。
449. 序列化和反序列化二叉搜索树
解法1：
二叉搜索树中不存在值相同的节点，所以可以通过前序和中序遍历通过二分递归反向推出这棵树。由于二叉搜索树是二叉树，所以也可以采用二叉树的普遍序列化方法。
下面是通过前序和中序遍历推出这棵树。
/**
* 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:
int num[2][10001],tot0,tot1;
void dfs(TreeNode* x){
if(x==NULL)return;
num[0][tot0++]=x->val;
dfs(x->left);
num[1][tot1++]=x->val;
dfs(x->right);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
tot0=0,tot1=0;
dfs(root);
char ch;
string ans;
for(int i=0;ir2)return NULL;
TreeNode* x=new TreeNode(num[0][l1]);
int m=l2;
for(;m<=r2;++m){
if(num[1][m]==num[0][l1])break;
}
x->left=dfs2(l1+1,l2,m-1);
x->right=dfs2(l1+(m-l2)+1,m+1,r2);
return x;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int size=data.size()/2;
for(int i=0;iserialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;
解法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:
int num[10001],tot;
void dfs(TreeNode* x){
if(x==NULL)return;
num[tot++]=x->val;
dfs(x->left);
dfs(x->right);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
tot=0;
dfs(root);
char ch;
string ans;
for(int i=0;ir)return NULL;
TreeNode* x=new TreeNode(num[l]);
int m=l;
for(;m<=r;++m){
if(num[m]>num[l])break;
}
x->left=dfs2(l+1,m-1);
x->right=dfs2(m,r);
return x;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int size=data.size();
for(int i=0;iserialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;
解法3：
由于二叉搜索树是二叉树，所以也可以采用二叉树的普遍序列化方法，此方法见下述297.二叉树的序列化与反序列化一题
297. 二叉树的序列化与反序列化
这道题有 BFS 和 DFS 两种方式。
BFS即层次建立二叉树。最后反序列化的时候用一个一个队列从另一个队列里逐个取出节点，被取的队列其实也可以用list。
/**
* 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:
TreeNode* q[20100]={};
int head=0,tail=0;
TreeNode* q1[20100]={};
int head1=0,tail1=0;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
head=0,tail=0;
q[tail++]=root;
string ans;
while(headval+1010)/100+1));
ans.push_back(char((x->val+1010)%100+1));
q[tail++]=x->left;
q[tail++]=x->right;
}
return ans;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
tail=head=0;
tail1=head1=0;
TreeNode *temp;
for(int i=0;ileft=q[head++];
q1[tail1++]=q[head];
x->right=q[head++];
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));