Serialize and Deserialize Binary Tree
問題概要
ある二分木が与えられるので、それを文字列にシリアライズして、その後またデシリアライズして元の二分木を作れ、という問題
解法
最初、LCA in Binary Treeを解いた時と同じような方針(つまりinorder, postorder順の巡回で得た値の配列を2つ作って、そこからシリアライズ・デシリアライズする)ことを考えたが、同じ値を持つノードがテストケースにあった場合にコケた 以下は解答AC時のコード
ただDFSで巡回して(多分巡回方法は何でも良い)シリアライズした後、同じ巡回順でデシリアライズすれば良いという感じだった
巡回方法が分かっているなら作る配列(文字列)は確かに1つで良い。
code:solution.cpp
/**
* 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) {
string ans = "";
traverse(root, ans);
ans.pop_back();
return ans;
}
void traverse(TreeNode* root, string& str) {
if (!root) {
str += "NULL,";
return;
}
str += to_string(root->val) + ",";
traverse(root->left, str);
traverse(root->right, str);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<string> data_list = split(data, ',');
reverse(data_list.begin(), data_list.end());
return des_traverse(data_list);
}
TreeNode* des_traverse(vector<string>& vec) {
if (vec.back() == "NULL") {
vec.pop_back();
return NULL;
}
TreeNode* node = new TreeNode(stoi(vec.back()));
vec.pop_back();
node->left = des_traverse(vec);
node->right = des_traverse(vec);
return node;
}
vector<string> split(string str, char del) {
int first = 0;
int last = str.find_first_of(del);
vector<string> result;
while (first < str.size()) {
string subStr(str, first, last - first);
result.push_back(subStr);
first = last + 1;
last = str.find_first_of(del, first);
if (last == string::npos) last = str.size();
}
return result;
}
};
2020/5/14の解き直しコード
code:resolve.cpp
/**
* 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:
string serialize(TreeNode* root) {
string ret = "";
preorder_traverse(root, ret);
return ret;
}
void preorder_traverse(TreeNode* node, string& ret) {
string val = (node) ? to_string(node->val) : "null";
ret += val + ',';
if (!node) return;
preorder_traverse(node->left, ret);
preorder_traverse(node->right, ret);
}
TreeNode* deserialize(string data) {
queue<string> q;
for (string s : split(data, ',')) q.push(s);
return preorder_construct(q);
}
TreeNode* preorder_construct(queue<string>& q) {
if (q.size() < 1) return NULL;
string top = q.front();
q.pop();
if (top == "null") return NULL;
TreeNode* node = new TreeNode(stoi(top));
node->left = preorder_construct(q);
node->right = preorder_construct(q);
return node;
}
vector<string> split(string str, char del) {
int first = 0;
int last = str.find_first_of(del);
vector<string> result;
while (first < str.size()) {
result.push_back(str.substr(first, last - first));
first = last + 1;
last = str.find_first_of(del, first);
if (last == string::npos) last = str.size();
}
return result;
}
};