二叉树的序列化与反序列化

二叉树的序列化与反序列化

297.二叉树的序列化与反序列化

//先序遍历求解
class Codec {
public:
    //将二叉树序列化为字符串
    string serialize(TreeNode* root) {
        string res;
        helper(root, res);
        return res;
    }
    //辅助函数，将二叉树存入string中
    void helper(TreeNode* root, string& s){
        if(root==NULL){
            s += "#,";
        }else{
            s += to_string(root->val) + ",";
            helper(root->left, s);
            helper(root->right, s);
        }
    }

    //将字符串反序列化为二叉树
    TreeNode* deserialize(string data) {
        //将字符串转化成链表
        list<string> lst;
        //借助一个字符串来控制","
        string str; 
        for(auto& ch : data){
            if(ch==','){
                lst.push_back(str);
                str.clear();
            }else{
                str.push_back(ch);
            }
        }
        if(!str.empty()){
            lst.push_back(str);
            str.clear();
        }
        return build(lst);
    }
    //辅助函数，通过链表构造二叉树
    TreeNode* build(list<string>& data){
        if(data.front()=="#"){
            data.erase(data.begin());
            return NULL;
        }

        TreeNode* root = new TreeNode(stoi(data.front()));
        data.erase(data.begin());
        root->left=build(data);
        root->right=build(data);
        return root;
    }
};