本文共 3610 字，大约阅读时间需要 12 分钟。

注意：序列化和反序列化只要能可逆就行，后面可以多出几个NULL

注意：string用+= 和push_back()效率要高于 用+，用+需要创建一个新的stirng对象

序列化：层序遍历

思想：

​ 逐层写入

复杂度：

​ ●时间：遍历每一个节点：O(n)

​ ●空间：O(n)，利用队列

代码：

// Encodes a tree to a single string.    string serialize(TreeNode* root) {           //询问面试官为空时是string是空还是有个NULL，为空则要加判root是否为空，为NULL则不用        queue
   
    my_queue;        my_queue.push(root);        string str_tree;        //层序遍历        while(!my_queue.empty()){               TreeNode* cur = my_queue.front();            my_queue.pop();            //不为空则写入            if(cur != NULL){                   str_tree += to_string(cur->val);                str_tree += ",";                my_queue.push(cur->left);                my_queue.push(cur->right);            }            else                str_tree += "NULL,";        }        //去掉最后的逗号        str_tree.pop_back();        return str_tree;    }
   

反序列化

思想：

​ 将string中的每个节点分隔开并放入vector<TreeNode*>，并利用vector<TreeNode*>重建

复杂度：

​ 这里获取单个字符串较为复杂，可以使用流的方式。

代码：

TreeNode* deserialize(string data) {           if(data.size() == 0)            return NULL;        int size_data = data.size();         //i用来遍历data        int i = 0;        vector
   
    vec_tree;        //将string转为vector
    
     来存储        while(i < size_data){               string str_cur = "";            while(i < size_data && data[i] != ','){                   str_cur.push_back(data[i]);                i++;            }            if(str_cur == "NULL")                vec_tree.push_back(NULL);            else{                   TreeNode* tmp = new TreeNode(stoi(str_cur));                vec_tree.push_back(tmp);            }            //跳过逗号            i++;        }        //画一下就能理解这个流程，i用来遍历父节点，j用来遍历子节点        for(int i = 0, j = 1; j < vec_tree.size(); i++){               if(vec_tree[i] == NULL)                continue;            //连接左子树            vec_tree[i]->left = vec_tree[j++];            //连接右子树，因为j加了1，所以需要判断            if(j < vec_tree.size())                vec_tree[i]->right = vec_tree[j++];        }        return vec_tree[0];    }
    
   

利用流序列化和反序列化

注意：

​ 这里是用空格间隔而不是用","，这样更方便获取str_cur，要用逗号序列化可以在反序列化时先把逗号转为空格

代码：

class Codec {   public:    // Encodes a tree to a single string.    string serialize(TreeNode* root) {           ostringstream out;        queue
   
    my_queue;        my_queue.push(root);        while(!my_queue.empty()){               TreeNode* cur = my_queue.front();            my_queue.pop();            if(cur != NULL){                   out<
    
     val<<" ";                my_queue.push(cur->left);                my_queue.push(cur->right);            }            else                out<<"NULL ";        }        return out.str();        }    // Decodes your encoded data to tree.    TreeNode* deserialize(string data) {           istringstream input(data);        string str_cur;        vector
     
      vec_node;        //利用流来获取单个字符        while(input >> str_cur){               if(str_cur == "NULL")                vec_node.push_back(NULL);            else                vec_node.push_back(new TreeNode(stoi(str_cur)));        }                                                 // i每往后移动一位，j移动两位，j始终是当前i的左子下标         // 肯定是j先到达边界，所以这里判断j < vec.size()        for (int i = 0, j = 1; j < vec_node.size(); ++i) {                   //某个NULL的下面一层还有别的节点时(类似于NULL为头节点)，如[1,N,2,N,N,3,4]就需要这里的判断            if (vec_node[i] == NULL) continue;                 // 当前j位置为i的左子树                          vec_node[i]->left = vec_node[j++];                // 当前j位置为i的右子树，j改变了，所以需要判断            if (j < vec_node.size())                 vec_node[i]->right = vec_node[j++];           }        return vec_node[0];    }};
     
    
   

转载地址：http://mndq.baihongyu.com/