数据结构之二叉树序列化和反序列化（含代码实现）

一 .重建二叉树

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

题目描述：

解题思路：

1.由于先序遍历序列空节点已经用‘#’表示出来所以我们可以递归还原二叉树，如果遇到‘#’则返回nullptr，否则就创建新的头节点，再递归构建他的左子树和右子树，构建完成后将头节点返回即可。

以序列 abc##d###为例（抱歉最后一个#放不下了）

1.首先来到头节点发现不是空创建节点：

然后递归创建它的左子树，再递归创建它的右子树。来到b不是#创建节点b.（少写了一个#抱歉）

来到下一个节点发现不是空创建节点c:

来到下一节点发现是#同理发现下一个节点也是# 返回空那么c就创建好了返回让b链上，再图中为了好看我提前将其链上了：

再到下一个节点发现不是的空创建：

然后再创建空（之前由于后面写不下了少写了一个#)下面也是同理的：

对应代码：

#include<string>
#include<iostream>
using namespace std;
class TreeNode{
  public:
    
   void Inorder(TreeNode*root){
        if(!root)return;
       Inorder(root->_left );
       cout<<root->val<<" ";
       Inorder(root->_right);
    }
    
    TreeNode(char ch)
    :_left(nullptr)
    ,_right(nullptr)
    ,val(ch)
    {}
    TreeNode*_left;
    TreeNode*_right;
    char val;
};

  TreeNode*CreatTree(const string&s,int &i){
              if(s[i]=='#'){//返回空
                  i++;
                  return nullptr;
              }
      
      TreeNode*root=new TreeNode(s[i++]);
      root->_left=CreatTree(s,i);//构建左树
      root->_right=CreatTree(s,i);//构建右树
      return root;//返回根节点
      
  }

int main(){
    string s;
    cin>>s;
    int i=0;
    TreeNode*root=CreatTree(s,i);
    root->Inorder(root);
    
    
}

二.二叉树序列化和反序列化

1. 二叉树的序列化与反序列化 - 力扣（LeetCode） (leetcode-cn.com)

题目描述：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root){
            return "#";
        }
    return to_string(root->val)+" "+serialize(root->left)+" "+serialize(root->right);//转换字符串
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data){
        istringstream ss(data);//分割字符串
      return buildTree(ss);
    }
    TreeNode*buildTree(istringstream&ss){
        string str;
        ss>>str;//读入字符串
        if(str=="#"){
         return NULL;
        }
        TreeNode*root=new TreeNode(stoi(str));//构建根节点
        root->left=buildTree(ss);//再构建左子树
        root->right=buildTree(ss);//构建右子树
        return root;//返回根节点
    }

};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

解题思路：

我们可以先将字符串转换成上题的形式再按照上面那题的方法进行还原即可。

对应代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root){
            return "#";
        }
    return to_string(root->val)+" "+serialize(root->left)+" "+serialize(root->right);//转换字符串
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data){
        istringstream ss(data);//分割字符串
      return buildTree(ss);
    }
    TreeNode*buildTree(istringstream&ss){
        string str;
        ss>>str;//读入字符串
        if(str=="#"){
         return NULL;
        }
        TreeNode*root=new TreeNode(stoi(str));//构建根节点
        root->left=buildTree(ss);//再构建左子树
        root->right=buildTree(ss);//构建右子树
        return root;//返回根节点
    }

};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

方法二：

层序遍历：先按照层序遍历的方法将其序列化为字符串。反序列化时：首先判断字符串是否为#如果是则返回空，不是空之后先创建头节点

并将其放入队列中在构建它的左孩子和右孩子，如果左孩子不为空则将其加入到队列中，右孩子不为空则将其加入到队列中，重复上述过程最后将其根节点返回即可。

对应代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
         string ans;
        if(root==NULL){
          return "#";
        }
    
        queue<TreeNode*>q;
        ans+=to_string(root->val);
        ans+=" ";//以空格作为分隔
        q.push(root);//将节点放入队列中
        while(!q.empty()){
           TreeNode*node=q.front();//取出头部数据
           q.pop();
           if(node->left){//左不为空
               q.push(node->left);//入站
               ans+=to_string(node->left->val);//将左孩子的值加入到字符串中
               ans+=" ";//以空格分隔
           }

           else{//空用#代表
               ans+="#";
               ans+=" ";
           }

           if(node->right){//右树不为空同理
               q.push(node->right);
               ans+=to_string(node->right->val);
               ans+=" ";
           }

           else{
               ans+="#";
               ans+=" ";
           }

        }

          return ans;//将字符串返回

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data=="#")return NULL;//如果确定是空树直接返回
    
        istringstream ss(data);//将字符串以空格分割
        vector<string>ans;
        string tmp;
        while(ss>>tmp){//将字符串放入容器中
            ans.push_back(tmp);
        }
        int i=0;
        TreeNode*root=new TreeNode(stoi(ans[i++]));//构建头节点
        queue<TreeNode*>q;
        q.push(root);//放入队列中
        while(!q.empty()){
            auto node=q.front();//取出头节点
            q.pop();
              if(ans[i]!="#")//如果不为空
             node->left=new TreeNode(stoi(ans[i]));//构建左子树
             else
             node->left=NULL;//否则就指向空
             i++;//i往后面走
            if(ans[i]!="#")//构建右子树
            node->right=new TreeNode(stoi(ans[i]));
            else
            node->right=NULL;
              i++;
            if(node->left){//不为空则继续放入队列中
                q.push(node->left);
            }
            if(node->right){
                q.push(node->right);
            }

        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

二叉树和N叉树的相互转换

1. 将 N 叉树编码为二叉树 - 力扣（LeetCode） (leetcode-cn.com)

解题思路：

将n叉树的所有孩子节点都放入左树右边界上即可，转换回来时先构建当前节点递归构建其孩子节点具体请看代码：

TreeNode* encode(Node* root) {
    if (root == NULL)
        return NULL;
    TreeNode* head = new TreeNode(root->val);
    head->left = en(root->children);
    return head;
}
TreeNode* en(vector<Node*>child) {
    TreeNode* head = nullptr;
    TreeNode* cur = nullptr;
    for (auto x : child) {
        TreeNode* tNode = new TreeNode(x->val);
        if (head == nullptr)
            head = tNode;
        else
            cur->right = tNode;
        
        cur = tNode;
        cur->left = en(x->children);//将左树右边界的头返回
    }
    return head;
}

Node* decode(TreeNode* root) {
    if (root == nullptr)
        return nullptr;
    return new Node(root->val, de(root->left));
}
vector<Node*>de(TreeNode* root) {
    vector<Node*>child;
    while (root) {
        Node* cur = new Node(root->val, de(root->left));//构建其孩子节点
        child.push_back(cur);
        root = root->right;
    }
    return child;
}