时间复杂度
我是先写的层次遍历的解法,然后再写的先序遍历解法
看到大家都是用的先序遍历,我把我的解法贴一下(虽然感觉写的并不好)
时间的话在acwing上提交的是24ms, 时间复杂度就不说了。
注意点:里面有个string类的data参数, 我开始没有用const string& , 结果内存暴增
C++ 代码
class Solution {
public:
// find the depth of the tree
int dfs(TreeNode* root)
{
return root ? max(dfs(root->left),dfs(root->right)) + 1 : 0;
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector<TreeNode*> notes;
string tree = "[";
if(!root)
return "[]";
notes.push_back(root);
vector<TreeNode*> backup;
int level = dfs(root);
while(level --)
{
for(int i = 0; i < notes.size(); i ++)
{
TreeNode* q = notes[i];
if(q)
{
tree += to_string(q->val) + ",";
backup.push_back(q->left);
backup.push_back(q->right);
}
else
{
tree += "#,";
}
}
notes.clear();
notes.assign(backup.begin(),backup.end());
backup.clear();
}
tree += "]";
return tree;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.compare(std::string{"[]"}) == 0)
return nullptr;
// data = data.substr(1);
// 根结点
int pos = data.find(",");
string note = data.substr(1,pos - 1);
int number = std::stoi(note);
// data = data.substr(pos+1);
pos ++;
TreeNode* root = new TreeNode(number);
queue<TreeNode*> tag;
tag.push(root);
while(data.length() > pos + 1)
{
int pos1 = data.find(",",pos);
string note1 = data.substr(pos,pos1 - pos);
// data = data.substr(pos1+1);
pos = pos1 + 1;
int pos2 = data.find(",",pos);
string note2 = data.substr(pos,pos2 - pos);
pos = pos2 + 1;
// data = data.substr(pos2+1);
TreeNode* last_tag = tag.front();
tag.pop();
while(last_tag == nullptr)
{
last_tag = tag.front();
tag.pop();
}
if(last_tag)
{
if(note1.compare(std::string{"#"}) != 0)
{
last_tag->left = new TreeNode(std::stoi(note1));
tag.push(last_tag->left);
}
else
tag.push(nullptr);
if(note2.compare(std::string{"#"}) != 0)
{
last_tag->right = new TreeNode(std::stoi(note2));
tag.push(last_tag->right);
}
else
tag.push(nullptr);
}
}
return root;
}
};