题解 | #序列化二叉树#
序列化二叉树
http://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84
序列化二叉树
问题描述：请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，可以根据层序遍历并特定标志空结点的方案序列化，也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。
假如一棵树共有 2 个结点， 其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。按照上面第一种说法可以序列化为“1,#,2,#,#”，按照上面第二种说法可以序列化为“{0:1,2:2}”，按照上面第三种说法可以序列化为“1,2;2,1”，这三种序列化的结果都包含足以构建一棵与原二叉树完全相同的二叉树的信息。
示例
输入：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}
方法一
思路分析
对于二叉树的遍历可以使用先序遍历、中序遍历、后序遍历以及层次遍历的方法，方法一介绍先序遍历的办法，先访问根节点，然后访问左子树，最后访问右子树，需要注意的是再访问根节点时如果根节点为空则使用“#”代替，并且节点之间田间逗号隔开。反序列化的时候由于采用先序遍历序列化，因此在反序列化时如果遇到“#”，则表示该节点为空，则该节点的左子树为空，开始构建右子树，如果再遇到"#"则表示该部分的右子树为空，即前一根节点的左子树为空，按照前序顺序，递归的使用字符串中的字符创建一个二叉树。
图解
序列化过程如下：
序列化后的为[1,2,4,#,#,5,#,#,3,#,#]
反序列化的过程：
- 根据前序遍历，根节点不为#，则该节点不为空，作为根节点
- 寻找下一个节点构建左子树，如果不为#，则继续向后构建左子树；
- 如果该节点为空，则上一根节点的左子树为空，向后寻找字符，如果再次碰到#，则上一根节点的右子树为空，以此循环
序列化中1作为根节点，向后寻找字符，由于采用前序遍历作为访问节点方式，2作为1的左子树，向后寻找字符，4作为2的左子树，向后寻找字符，遇到#，则表示4的左子树为空，向后寻找遇到#，4的右子树为空，此时说明2的左子树部分完成，那么下一个字符5作为2的右子树，后面两个#说明5的左右子树为空，此时1的左子树构建完成，继续后见1的右子树，3作为1的右子树，之后的两个#，说明3的左右子树为空，构建成功。
反序列化图解如下：
C++核心代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
char* Serialize(TreeNode *root) {
if(root== NULL)
return NULL;
string str;
Serialize(root,str);
char *ret = new char[str.length()+1];
int i ;
for( i = 0;i < str.length();i++)
{
ret[i] = str[i];
}
ret[i] = '\0';
return ret;
}
void Serialize(TreeNode *root,string &str)
{
if(root == NULL)
{
str += '#';//根节点为空使用#代替
return ;
}
string s = to_string(root->val);
str += s;
str += ',';//节点之间使用,隔开
Serialize(root->left,str);//递归左子树
Serialize(root->right,str);//递归访问右子树
}
TreeNode* Deserialize(char *str) {
if(str == NULL)
return NULL;
TreeNode* ret = Deserialize(&str);
return ret;
}
TreeNode *Deserialize(char **str)
{
if(**str == '#')//遇到#表示节点为空
{
++(*str);
return NULL;
}
int num = 0;
while(**str != '\0' && **str !=',')
{
num = num*10 + ((**str) - '0');
++(*str);
}
TreeNode *root = new TreeNode(num);
if(**str == '\0')
return root;
else
(*str)++;
root->left = Deserialize(str);//按照前序遍历递归左子树的使用字符构建二叉树
root->right = Deserialize(str);//按照前序遍历递归右子树的使用字符构建二叉树
return root;
}
}; 复杂度分析
- 时间复杂度：先序遍历时间复杂度最大为二叉树是一个只有左子树或者只有右子树，此时时间复杂度为$O(n)$
- 空间复杂度：先序遍历使用递归方法，空间复杂度为$O(n)$
方法二
思路分析
对于二叉树的访问还可采用层序遍历的办法，遍历二叉树时从上到下、从左到右按层进行遍历，在遍历过程中需要用到队列，序列化过程如下：
- 首先将二叉树的根节点push到队列中，判断队列不为NULL，就队头的元素值到序列化值中
- 判断节点如果有孩子，就将孩子的值增加到序列化值中，并将孩子节点push到队列中
- 遍历过的节点出队列
- 循环直到二叉树为空
- 层序遍历的过程中遇到空节点使用#代替
反序列化过程就是按照层序遍历再走一遍即可。
C++核心代码
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
char* Serialize(TreeNode *root) {
string str;
queue<TreeNode*>q;
q.push(root);
while(q.size())
{
TreeNode* tmp=q.front();
q.pop();
if(tmp==NULL) str+="#,";//空节点使用#代替
else
{
str+=to_string(tmp->val)+",";//节点之间使用逗号隔开
q.push(tmp->left);
q.push(tmp->right);
}
}
char* ans=new char[str.length()+1];//多一位存放'\0'
strcpy(ans,str.c_str());
return ans;
}
TreeNode* Deserialize(char *str){
if(str==NULL||str[0]=='#') return NULL;
string s(str);
queue<TreeNode*>q;
TreeNode* ans=new TreeNode(atoi(s.c_str()));
s=s.substr(s.find_first_of(',')+1);
q.push(ans);
while(q.size()&&s.size())
{
TreeNode* tmp=q.front();//根节点
q.pop();
//左子树
if(s[0]=='#')
{
tmp->left=NULL;
s=s.substr(2);
}
else
{
tmp->left=new TreeNode(atoi(s.c_str()));
q.push(tmp->left);
s=s.substr(s.find_first_of(',')+1);
}
//右子树
if(s[0]=='#')
{
tmp->right=NULL;
s=s.substr(2);
}
else
{
tmp->right=new TreeNode(atoi(s.c_str()));
q.push(tmp->right);
s=s.substr(s.find_first_of(',')+1);
}
}
return ans;
}
}; 复杂度分析
- 时间复杂度：时间复杂度与前序遍历相同，只是打印顺序的问题，因此为$O(n)$
- 空间复杂度：借助于一个队列实现层序遍历，因此为$O(n)$
