问题描述
lintcode
参考
Serialization/Deserialization of a Binary Tree
LintCode Binary Tree Serialization
笔记
可以用
先序遍历
和
使用"#"来表示NULL
的方法来序列化,最后也用先序遍历来反序列化。
代码
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
string serialize(TreeNode *root) {
// write your code here
string s = "";
writeTree(s, root);
return s;
}
void writeTree(string &s, TreeNode* root)
{
if (root == NULL)
{
s += "# ";
return;
}
s += (to_string(root->val) + ' ');
writeTree(s, root->left);
writeTree(s, root->right);
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
TreeNode *deserialize(string data) {
// write your code here
int pos = ;
return readTree(data, pos);
}
TreeNode* readTree(string data, int& pos)
{
if (data[pos] == '#')
{
pos += ;
return NULL;
}
int nownum = ;
while (data[pos] != ' ')
{
nownum = nownum * + (data[pos] - '0');
pos++;
}
pos++;
TreeNode* nowNode = new TreeNode(nownum);
nowNode->left = readTree(data, pos);
nowNode->right = readTree(data, pos);
return nowNode;
}
};