题目描述
请实现两个函数,分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串,并且可以将此字符串反序列化为原始树结构。
样例
你可以序列化如下的二叉树
8
/ \
12 2
/ \
6 4
为:"[8, 12, 2, null, null, 6, 4, null, null, null, null]"
时间复杂度 O(n)
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
if(!root) return res;
queue<TreeNode* > q;
q.push(root);
while(q.size())
{
auto a = q.front();
q.pop();
if(!a)
res += "null ";
else
{
res += to_string(a->val) + ' ';
q.push(a->left);
q.push(a->right);
}
}
return res;
}
// Decodes your encoded data to tree.
string data;
int s = 0;
TreeNode* deserialize(string _data) {
data = _data;
if(!data.size()) return nullptr;
auto root = new TreeNode(atoi(fstr().c_str()));
queue<TreeNode* > q;
q.push(root);
while(s < data.size())
{
auto a = q.front();
q.pop();
string left = fstr();
string right = fstr();
if(left != "null")
{
a->left = new TreeNode(atoi(left.c_str()));
q.push(a->left);
}
if(right != "null")
{
a->right = new TreeNode(atoi(right.c_str()));
q.push(a->right);
}
}
return root;
}
string fstr()
{
string temp;
int k = s;
while(data[k] != ' ') k++;
if(data[s] == 'n')
{
temp = "null";
s = k + 1;
}
else
{
int res = 0;
for(int i = s; i < k; i++) temp += data[i];
s = k + 1;
}
return temp;
}
};