297. serialize and deserialize binary tree
grind75题随便写
用preorder放 然后再拿出来
原本在想要区分nullptr所以分了4种case
其实空格切一切 摆个符号就好了==
看solution原来 stringstream 能用
印象中开这个会跑很慢？
/**
* 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:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root == nullptr) return "";
if(root->left == nullptr){
if(root->right == nullptr){
//type a :00
cout << root->val << ";a, ";
return to_string(root->val) + ";a,";
}
else{
//type b:01
cout << root->val << ";b, ";
return to_string(root->val) + ";b," + serialize(root->right);
}
}
if(root->right == nullptr){
//type c:10
cout << root->val << ";c, ";
return to_string(root->val) + ";c," + serialize(root->left);
}
else {
// type d:11
cout << root->val << ";d, ";
return to_string(root->val) + ";d," + serialize(root->left) + serialize(root->right);
}
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data == "") return nullptr;
cout << endl << data << endl;
//char delimiter_val = ";" char delimiter_type = ","
queue<int> vals;
queue<char> types;
std::string::size_type begin, end;
end = data.find(";");
begin = 0;
while(end != std::string::npos){
if (end - begin != 0) {
vals.push( stoi( data.substr( begin, end - begin)));
}
begin = end + 1;
end = data.find(",", begin);
if (end - begin != 0){
types.push( data.substr( begin, end - begin)[0]);
}
begin = end + 1;
end = data.find(";", begin);
}
TreeNode* mutsumi = new TreeNode();
Build_A_Small_Tree(vals, types, mutsumi);
return mutsumi;
}
TreeNode* Build_A_Small_Tree(queue<int>& vals, queue<char>& types, TreeNode* root){
if(vals.empty()) return root;
root->val = vals.front();
vals.pop();
char t = types.front();
types.pop();
if(t=='b'){
root->right = Build_A_Small_Tree(vals, types, new TreeNode());
}
else if(t=='c'){
root->left = Build_A_Small_Tree(vals, types, new TreeNode());
}
else if(t=='d'){
root->left = Build_A_Small_Tree(vals, types, new TreeNode());
root->right = Build_A_Small_Tree(vals, types, new TreeNode());
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));