剑指OFFER 序列化二叉树
弄了半天在剑指OFFER OJ上无法通过(猜测可能是因为剑指OFFER上使用的是char类型的指针,导致有一些编译的不一致问题),同样的代码在leetcode上通过了
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
int pos = 0;
string str;
string res;
void recur_from_order(TreeNode* &node)
{
if(str[pos] == '#'){
node = NULL;
return;
}else{
string str_num;
while(str[pos] != '!')
{
str_num += str[pos];
pos++;
}
//int num = stoi(str_num);
int num = atoi(str_num.c_str());
node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = num;
}
pos++;
recur_from_order(node->left);
pos++;
recur_from_order(node->right);
}
void recur_to_order(TreeNode *node)
{
if(node == NULL){
res += '#';
return;
}else{
res += to_string(node->val);
res += '!';
}
recur_to_order(node->left);
recur_to_order(node->right);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
recur_to_order(root);
return res;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
str = data;
TreeNode* ret;
recur_from_order(ret);
return ret;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
采用的先序遍历的方式,先写序列化的代码,就是先序遍历一遍,遇到结点就记录到res中.
反序列化稍微复杂一点,聚焦于两个状态,一个是结点,一个是字符串的位置指针,通过这两个状态来构建二叉树.