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

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 示例：你可以将以下二叉树： 1 / \ 2 3 / \ 4 5 序列化为 “[1,2,3,null,null,4,5]” 提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

解题思路

序列化和反序列化之间的约定：二叉树的前序遍历/中序遍历/后序遍历/层次遍历
序列化：按遍历约定遍历二叉树，将空结点记为字符“n”,并用字符“,”作为分隔符，分隔每个结点的值
反序列化：先将序列化的字符串分割成单个结点值到容器中，顺序遍历容器，同时按二叉树的遍历约定递归建立二叉树
实现细节
1.分割字符串
使用stringstream和getline函数来实现对字符串的分割

 string data = "1,2,3,null,null,4,5";
 vector<string> treeVec;
 stringstream ss;
 ss << data;
 string temp;
 while(getline(ss, temp, ','))
 {
     treeVec.push_back(temp);//和python里的split一个功能
 }

或者自己实现split函数

void split(const string& s,vector<string>& tokens,const string& delimiters=""){
    string::size_type lastPos =s.find_first_not_of(delimiters,0);
    string::size_type pos =s.find_first_of(delimiters,lastPos);
    while(string::npos != pos || string::npos != lastPos){
        tokens.push_back(s.substr(lastPos, pos- lastPos));//use empLace back after c 
        lastPos = s.find_first_not_of(delimiters,pos);
        pos=s.find_first_of(delimiters,lastPos);
    }
}
vector<string> treeVec;
string delimiters = ",";
split(data,treeVec,delimiters);

序列化和反序列化都可以使用递归或者迭代，但是发现序列化用递归实现会超时，用迭代会快很多。 ```cpp /
- Definition for a binary tree node.
- struct TreeNode {
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- }; */
  include
  class Codec { public: string serialize(TreeNode root) { string ret; stack<TreeNode> s; s.push(root); while(!s.empty())//这个步骤和先序是u一样 {
```
   TreeNode* p = s.top();
   s.pop();
   if(p) {
           s.push(p->right);
          s.push(p->left);
         ret += to_string(p->val) + ",";
         }
   else
       ret += "n,";
```
  } ret.erase(ret.end()-1);//把尾巴上多的一个逗号去掉 return ret; } TreeNode* desDep(vector
  & treeVec,int& pos){ if( treeVec[pos] == “n”){
```
   pos++;
   return NULL;
```
  } TreeNode root = new TreeNode(stoi(treeVec[pos])); pos++; root->left = desDep(treeVec,pos); root->right = desDep(treeVec,pos); return root; } // Decodes your encoded data to tree. TreeNode deserialize(string data) { vector
  treeVec; stringstream ss; ss << data; string temp; while(getline(ss, temp, ‘,’)) {
```
   treeVec.push_back(temp);//和python里的split一个功能
```
  } int pos = 0; return desDep(treeVec,pos); } };

// Your Codec object will be instantiated and called as such: // Codec codec; // codec.deserialize(codec.serialize(root)); ```

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

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

解题思路

include