题目描述
请实现两个函数,分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。
数据范围
树中节点数量 [0,1000]。
样例
你可以序列化如下的二叉树
8
/ \
12 2
/ \
6 4
为:"[8, 12, 2, null, null, 6, 4, null, null, null, null]"
注意:
以上的格式是AcWing序列化二叉树的方式,你不必一定按照此格式,所以可以设计出一些新的构造方式。
算法1
(自己的写法,BFS)
没什么特别难想的地方,就是需要把代码分块,写成几个函数就好了。
注意的地方:
1.负数的处理
2.由队列生成树的时候,采用了队列的形式
C++ 代码
class Solution {
public:
void add_number(string &s, int num)//这里一定注意处理负数
{
int temp = num;
if(temp<0) temp = -temp;
while(temp)
{
s.push_back(temp %10+'0');
temp /= 10;
}
if(num<0) s+='-';
}
// Encodes a tree to a single string.
string serialize(TreeNode* root)
{
//使用BFS进行层序遍历
string res;
if(!root) return res;
queue<TreeNode *> q;
q.emplace(root);
while(!q.empty())
{
int sz = q.size();
for(int i=0;i<sz;++i)
{
auto cur = q.front();
q.pop();
if(cur == nullptr)
{
res+= '!';
res+=',';
}
else
{
add_number(res, cur->val);
res += ',';
}
if(cur != nullptr)
{
q.emplace(cur->left);
q.emplace(cur->right);
}
}
}
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data)
{
if(data.empty()) return nullptr;
queue<TreeNode *> q;
int num=0;
int temp =1;
char pre;
//将字符串变为队列
for(int i=0;i!=data.size();++i)
{
if(data[i] == ',' )
{
auto node = new TreeNode(num);
q.emplace(node);
num =0;
temp =1;
}
else if(data[i] == '!')
{
q.emplace(nullptr);
num =0;
temp =1;
i++;
}
else
{
if(data[i]== '-') //处理负数
{
num=-num;
continue;
}
num += (data[i]-'0')* temp ;
temp = temp*10;
}
}
//将队列变为树
auto head =dfs(q);
return head;
}
TreeNode * dfs(queue<TreeNode *> &lib)
{
TreeNode *head = lib.front();
queue<TreeNode *> q;
q.emplace(lib.front());
lib.pop();
while(!q.empty())
{
int sz= q.size();
if(lib.empty()) break;
for(int i=0;i<sz;++i)
{
auto cur = q.front();
q.pop();
if(cur!=nullptr)
{
cur->left = lib.front();
lib.pop();
q.emplace(cur->left);
cur->right=lib.front();
lib.pop();
q.emplace(cur->right);
}
}
}
return head;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla