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

目录

一 .重建二叉树 

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

---

一 .重建二叉树 

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

题目描述：

 解题思路：

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

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

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

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

 

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

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

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

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

 

 对应代码：

#include
#include
using namespace std;
class TreeNode{public:void Inorder(TreeNode*root){if(!root)return;Inorder(root->_left );cout<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);}

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

297. 二叉树的序列化与反序列化 - 力扣（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 "#";}queueq;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);//将字符串以空格分割vectorans;string tmp;while(ss>>tmp){//将字符串放入容器中ans.push_back(tmp);}int i=0;TreeNode*root=new TreeNode(stoi(ans[i++]));//构建头节点queueq;q.push(root);//放入队列中while(!q.empty()){auto node=q.front();//取出头节点q.pop();if(ans[i]!="#")//如果不为空node->left=new TreeNode(stoi(ans[i]));//构建左子树elsenode->left=NULL;//否则就指向空i++;//i往后面走if(ans[i]!="#")//构建右子树node->right=new TreeNode(stoi(ans[i]));elsenode->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叉树的相互转换

431. 将 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(vectorchild) {TreeNode* head = nullptr;TreeNode* cur = nullptr;for (auto x : child) {TreeNode* tNode = new TreeNode(x->val);if (head == nullptr)head = tNode;elsecur->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));
}
vectorde(TreeNode* root) {vectorchild;while (root) {Node* cur = new Node(root->val, de(root->left));//构建其孩子节点child.push_back(cur);root = root->right;}return child;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！