您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

新手花了一下午终于写出来BFS的序列化与反序列化!!!

文章目录

  • 题目
  • 解题思路
  • 代码

题目

在这里插入图片描述

初看题目可能会很懵逼,实际上就是一个把二叉树的数据-->字符串,然后通过这个字符串又能转为原来的二叉树。

解题思路

  1. 序列化:用','对每个数值进行分割,碰到null将其表示为'X'
  2. 反序列化:需要三个过程:<1>把原来的字符串进行分割成单独的数据(不存在',')。<2>把字符串转为int型整数。<3>进行反序列化过程,用一个sum、count变量存储相应信息,对第一步的列表进行遍历制造层序二叉树,这个过程同样也需要用到第二步的字符串转整数过程(得到每个结点的值的函数)

代码

class Codec {
public:
    string serialize(TreeNode* root) {
        queue<TreeNode*>Q;
        Q.push(root);
        string res;
        while(!Q.empty()){
           //由于不需要基于每层对某个数据单独处理,所以没必要设置每层的for...
                TreeNode* t = Q.front();
                Q.pop();
                //为了体现null,并且是保持层序的顺序则需要把null入队,那么就需要对其特殊对待
                if(t){
                res += to_string(t->val)+',';
                    Q.push(t->left);
                    Q.push(t->right);}
                else{
                    res += "X,";
                }
        }
        return res;
    }
    //利用','把string分割成多个数值的列表
vector<string> split(string& s){
    vector<string> res;
    string temp = "";
    for(char t:s){
        if(t==','){
            res.push_back(temp);
            temp = "";
            continue;
        }
        temp.push_back(t);
    }
    return res;
}//把分割好的各个字符串转为数字的函数
int get_int(string& s){
    stringstream ss;
    int res;
    ss<<s;
    ss>>res;
    return res;
}
    TreeNode* deserialize(string data) {
        //当要反序列化的date是null时,需要特殊处理
        if(data.empty()||data[0]=='X')
            return nullptr;
        //将date字符串分割为单个数据存储入vector容器
        vector<string> values = split(data);
        int len = values.size();
        queue<TreeNode*>Q;
        TreeNode* root = new TreeNode(get_int(values[0]));
        Q.push(root);
        //sum表示到该层和前面层的所有元素的个数总和,由于当前层是第一层,所以sum = 1
        int sum = 1;
        while(!Q.empty()){
            int count = 0;//用于记录每层已经处理过的元素个数
        //很明显count和sum需要基于每层进行更新所以需要每层的限制循环for...
            for(int i=Q.size();i>0;i--){
                TreeNode* t = Q.front();
                Q.pop();
//开始恢复树形结构,和序列化的过程一样无论它的子结点是否存在(通过判断是否为'X'),都入队,以保证顺序和整个元素的个数不变,所以处理当前结点的时候就需要分情况处理。
//一旦t为实质的结点(不为null)就执行插入过程,并且同一层的需要用count计算连接的相应元素。
//一旦遍历到null结点,不用管
                if(t){
                int index = sum-1+count;
                if(index+1<len){
                    if(values[index+1]!="X"){
                        int value = get_int(values[index+1]);
                        TreeNode* l = new TreeNode(value);
                        t->left = l;
                        Q.push(l);
                    }else{
                        t->left = nullptr;
                        Q.push(nullptr);
                    }
                }if(index+2<len){
                    if(values[index+2]!="X"){
                        int value = get_int(values[index+2]);
                        TreeNode* r = new TreeNode(value);
                        t->right = r;
                        Q.push(r);
                    }else{
                        t->right = nullptr;
                        Q.push(nullptr);
                    }  
                }//表示已经把下一层的元素使用了两个
                count += 2;
                }
            }
            //更新该层之前和该层所有元素个数
            sum += Q.size();
        }
        return root;
    }
};

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进