题目描述

请实现两个函数,分别用来序列化和反序列化二叉树
 
二叉树的序列化是指:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串,从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改,序列化的结果是一个字符串,序列化时通过 某种符号表示空节点(#),以 ! 表示一个结点值的结束(value!)。

二叉树的反序列化是指:根据某种遍历顺序得到的序列化字符串结果str,重构二叉树。
 
思路:
思路的话,题目已经说的很直白了。有一点要注意,fun2的参数应该是指针引用类型或者是一个二级指针,用string挺好的,但牛客题目中只给了char *。
代码如下:
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<int> vec;
    void fun1(TreeNode * root){
        if(root==NULL)
            vec.push_back(0xFFFFFFFF);
        else{
            vec.push_back(root->val);
            fun1(root->left);
            fun1(root->right);
        }
    }
    char* Serialize(TreeNode *root) {
        vec.clear();
        fun1(root);
        int sizes=vec.size();
        int * rev=new int[sizes];
        for(int i=0;i<sizes;i++)
            rev[i]=vec[i];
        return (char *)rev;
    }
    TreeNode * fun2(int * * nums){
        if((**nums)==0xFFFFFFFF)
        {
            (*nums)++;
            return NULL;
        }
        TreeNode * rev=new TreeNode(**nums);
        (*nums)++;
        rev->left=fun2(nums);
        rev->right=fun2(nums);
        return rev;
    }
    TreeNode* Deserialize(char *str) {
        int * nums=(int *)str;
        return fun2(&nums);
    }
};
 
12-19 10:36