题目描述
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，可以根据层序遍历并特定标志空结点的方案序列化，也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。
假如一棵树共有 2 个结点， 其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。按照上面第一种说法可以序列化为“1,#,2,#,#”，按照上面第二种说法可以序列化为“{0:1,2:2}”，按照上面第三种说法可以序列化为“1,2;2,1”，这三种序列化的结果都包含足以构建一棵与原二叉树完全相同的二叉树的信息。
不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。
考察知识点: 二叉树的四种遍历,前序遍历，中序遍历，后序遍历，层序遍历
首先介绍一下这四种遍历的思想
前序遍历：根结点 ---> 左子树 ---> 右子树
如图为前序遍历的遍历顺序举例:
中序遍历：左子树---> 根结点 ---> 右子树
如图为中序遍历的遍历顺序举例:后序遍历：左子树 ---> 右子树 ---> 根结点
如图为后序遍历的遍历顺序举例:
层次遍历：只需按层次遍历即可
如图为层序遍历的遍历顺序举例:
由题目描述我们可以选取任意的遍历方式解答，我使用两种思路实现前序遍历供大家参考
方法一:递归实现前序遍历
前序遍历的思路可以用递归的方式实现，实现代码大致框架为
void pre_order(TreeNode *root) {
if (!root) {
return; //判断根节点是否为空
}
cout << root->val ; //遍历根节点
pre_order(root->left); //遍历左子树
pre_order(root->right); //遍历右子树
}题目第一个函数要求我们讲二叉树序列化，故我们可以直接通过前序遍历完成，
代码及注释如下:
因为题目给定的函数是返回字符指针，不方便答案的拼接，故可以自行实现一个用string实现的函数然后单独处理结果的拼接
string Myseri(TreeNode* root){
if(!root) return "#!"; //判断根是否为空
//遵从根节点 --> 左子树 --> 右子树遍历顺序遍历
string str = to_string(root->val) + "!" + Myseri(root->left) + Myseri(root->right);
return str;
}
char* Serialize(TreeNode *root) { //将答案转换成char*型
string str = Myseri(root);
char* res = new char[str.size()];
for(int i=0; i<str.size(); i++){
res[i] = str[i];
}
return res;
}第二个函数是要求根据给定序列还原二叉树结构，实现的思路依旧是前序遍历，遵循前序遍历的思想，我们对给定的序列优先构造根节点，然后左子树，最后右子树的顺序，即可还原出正确的二叉树
代码与注释如下
class Solution {
public:
string Myseri(TreeNode* root){
if(!root) return "#!"; //空树直接返回
//遵从根节点 --> 左子树 --> 右子树遍历顺序遍历
string str = to_string(root->val) + "!" + Myseri(root->left) + Myseri(root->right);
return str;
}
TreeNode* MyDes(char *&str) {
if(*str == '#'){ //空串直接返回
str++;
return nullptr;
}
int cnt = 0;
while(*str != '!'){ //获取需要构建的节点中存储的数字
cnt = cnt * 10 + *str - '0';
str++;
}
TreeNode* node = new TreeNode(cnt); //构建当前节点
node->left = MyDes(++str); //构建左子树
node->right = MyDes(++str); //构建右子树
return node;
}
//将答案转换成char*型
char* Serialize(TreeNode *root) {
string str = Myseri(root);
char* res = new char[str.size()];
for(int i=0; i<str.size(); i++){
res[i] = str[i];
}
return res;
}
TreeNode* Deserialize(char *str){
return MyDes(str);
}
};时间复杂度:空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。时间复杂度应该为O(n)，根据公式T(n)=2T(n/2)+1=2(2T(n/4)+1)+1=2^logn+2^(logn-1)+...+2+1 ~= n，所以时间复杂度为O(n)。
方法二: 使用迭代实现前序遍历
原理与第一种方法相同，只是实现方式改变，与递归相比，迭代所耗费的时间与空间会更小，但是通常递归实现的代码比迭代更加简洁
代码及注释如下:
class Solution {
public:
char* Serialize(TreeNode *root) {
char* ans;
string str;
stack<TreeNode*> tmp; //使用栈模拟遍历过程
if (!root) { //空树直接返回
ans = new char[1];
*ans = '\0';
return ans;
}
while (root || tmp.size()) {
//优先将左子树遍历完
while (root) {
str += to_string(root->val) + '!';
tmp.push(root);
root = root->left;
}
str += '#';
//然后遍历遍历右子树
if (tmp.size()) {
root = tmp.top();
tmp.pop();
root = root->right;
}
}
str += '#';
ans = new char[str.size() + 1];
str.copy(ans, str.size(), 0);
return ans;
}
TreeNode* Deserialize(char *str) {
TreeNode* nodes = nullptr;
string arr;
stack<TreeNode**> s;
s.push(&nodes);
while (*str != '\0' && !s.empty()) {
if(*str == '#') s.pop();
else if (*str == '!') {
//栈顶指针指向新建节点
TreeNode* p = new TreeNode(stoi(arr));
*s.top() = p;
//先序遍历，根节点弹出，左右子树倒序入栈
s.pop();
s.push(&p->right);
s.push(&p->left);
arr.clear();
}
else arr += *str;
str ++ ;
}
return nodes;
}
};
京公网安备 11010502036488号