AcWing 50. 序列化二叉树
原题链接
困难
作者:
废wù
,
2021-02-03 22:13:36
,
所有人可见
,
阅读 342
class Solution {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(nullptr == root) return "";
queue<TreeNode*> tmp;
tmp.push(root);
string res = "[";
while(!tmp.empty()) {
int size = tmp.size();
for(int i=0; i<size; i++) {
if(nullptr != tmp.front()) {res.append(to_string(tmp.front()->val));res.append(",");}
else {res.append("null,"); tmp.pop(); continue;}
if(nullptr != tmp.front()->left) tmp.push(tmp.front()->left);
else tmp.push(nullptr);
if(nullptr != tmp.front()->right) tmp.push(tmp.front()->right);
else tmp.push(nullptr);
tmp.pop();
}
}
res[res.size()-1] = ']';
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.empty()) return nullptr;
string d(data.begin()+1, data.end());//去掉"["
d[d.size()-1] = ',';//将"]"换成","
vector<TreeNode*> parents;
int i = 0;
while(d[i] != ',') i++;//找到第一个数值
TreeNode* root = new TreeNode(atoi(string(d.begin(), d.begin()+i).c_str()));
i++;
parents.push_back(root);
vector<string> tmp;
while(i<d.size()) {
int j = i;
for(int count=0; count<2*parents.size() && j<d.size();count++) {
string value;
while(d[j] != ',' && j<d.size()) value.push_back(d[j++]);
j++;
tmp.push_back(value);
}//找到字节点数值字符串
parents = func(parents, tmp);//创建并返回子节点,父节点指向子节点
tmp.clear();
i = j;
}
return root;
}
private:
vector<TreeNode*> func(vector<TreeNode*> parents, vector<string>& childs)
{
vector<TreeNode*> res;
int p = 0, c = 0;
while(c != childs.size() && p<parents.size()) {
if(nullptr == parents[p]) {p++; continue;}
TreeNode* node = nullptr;
if(childs[c] != "null") {
node = new TreeNode(atoi(childs[c].c_str()));
}
if(c&1) parents[p++]->right = node;
else parents[p]->left = node;
if(nullptr != node) res.push_back(node);
c++;
}
return res;
}
};