LintCode 7 二叉树的序列化和反序列化

2019-11-08 19:53:49

字体：大中小

来源：转载

供稿：网友

题目:serialize and deserialize

要求:

设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。

样例:

给出一个测试数据样例，二叉树{3,9,20,#,#,15,7}，表示如下的树结构： 3 / /9 20 / / 15 7输入{1,#,2}输出{1,#,2}

算法要求:

无

解题思路:

需要了解什么是二叉树，其序列化和反序列化是什么。这道题的序列化和反序列化都是用先序遍历来进行的。首先，我们需要解析字符串，提取出有用的部分，存在vector容器中，再利用create函数进行递归建立二叉树。本题的难点在于，解析字符串和输出字符串的处理。

算法如下:

public: string serialize(TreeNode *root) {//反序列化 stringstream data; data << "{"; data << serialize2(root); data << "}"; string temp = data.str(); string::iterator itStr; itStr = temp.end(); itStr-=2; //去除结尾多余的,和# while (itStr != temp.begin()) { if (*itStr == '#') { temp.erase(itStr); } else if (*itStr == ',') { temp.erase(itStr); } else { break; } itStr--; } return temp; } TreeNode *deserialize(string data) {//序列化 if (data.size() == 2) { return NULL; } int start = data.find('{', 0); int end = data.find(',', 0); nums.clear();//清空容器 string tempStr = data.substr(start + 1, end - start - 1); //如果没有找到,相当于到了最后一个数，(start + 1)为数字位置，（data.size()- start - 2）为数字长度 if (end == -1) { tempStr = data.substr(start + 1, data.size()- start - 2); } else { tempStr = data.substr(start + 1, end - start - 1); } nums.push_back(tempStr); while (end != -1) { start = end; end = data.find(',', start+1); //如果没有找到,相当于到了最后一个数，(start + 1)为数字位置，（data.size()- start - 2）为数字长度 if (end == -1) { tempStr = data.substr(start + 1, data.size()- start - 2); } else { tempStr = data.substr(start + 1, end - start - 1); } nums.push_back(tempStr); } it = nums.begin(); TreeNode *root = creat(root); return root; }PRivate: vector<string> nums; vector<string>::iterator it; string serialize2(TreeNode *root) {//递归先序遍历，并返回字符串 // write your code here stringstream data;//此为字符串流，用法语cout,cin相似，集二者为一体,在这里用是为了方便操作 if (root == NULL) { data << "#,"; return data.str(); } data << root->val << ','; data << serialize2(root->left); data << serialize2(root->right); return data.str(); } int stoi(string str) {//字符串转化为整型 int num; stringstream ss;//此为字符串流，用法语cout,cin相似，集二者为一体，在这里用是为了整型转换 ss << *it; ss >> num; return num; } TreeNode *creat(TreeNode *bt) {//先序遍历，递归创建 if (it == nums.end()) {//因为序列化需要将多余的#省略，所以如果字符串结束，那么代表后面全是空结点。 return NULL; } if (*it == "#") { it++; return NULL; } else { bt = new TreeNode(stoi(*it)); it++; bt->left = creat(bt->left); bt->right = creat(bt->right); return bt; } }

上一篇：初学Linux（二）---Linux下C语言中的数组与指针

下一篇：matlab绘制海洋图