没什么好说的,
序列化:前序遍历,中序遍历 存到字符串
反序列化:把字符串转化为数组,然后就是重建二叉树那题了
反序列化的时候记得注意 负号!!!!
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
string res;
unordered_map<int, int> hash;
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
predfs(root);
indfs(root);
//cout << res << endl;
return res;
}
void predfs(TreeNode* root) {
if(!root) return;
res += to_string(root->val) + " ";
predfs(root->left);
predfs(root->right);
}
void indfs(TreeNode* root) {
if(!root) return;
indfs(root->left);
res += to_string(root->val) + " ";
indfs(root->right);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<int> num;
int temp = 0;
int flag = 1;
for(int i = 0; i < data.size(); i ++) {
if(data[i] == ' '){
num.push_back(temp);
//cout << temp << endl;
temp = 0;
flag = 1;
continue;
}
if(data[i] == '-'){
flag = -1;
continue;
}
temp = temp*10 + int(data[i]-'0')*flag;
}
for(int i = num.size()/2; i < num.size();i++){
hash[num[i]] = i;
}
return dfs(num,0,num.size()/2-1,num.size()/2,num.size()-1);
}
TreeNode* dfs(vector<int> &num,int pl, int pr, int il, int ir) {
if(pl > pr) return nullptr;
auto root = new TreeNode(num[pl]);
int k = hash[num[pl]] - il;
root -> left = dfs(num,pl+1,pl+1+k-1,il,il+k-1);
root -> right = dfs(num,pl+k+1,pr,il+k+1,ir);
return root;
}
};