作者sixB (6B)
標題Re: [閒聊] 每日leetcode
時間2024-05-17 07:25:35
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));
-----
Sent from JPTT on my iPad
--
很姆的咪
姆之咪
http://i.imgur.com/5sw7QOj.jpg
--
※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://ptt-website.tw/Marginalman/M.1715901941.A.2A5
推 SecondRun: 大師 05/17 07:31
