题解 | #序列化二叉树#
序列化二叉树
http://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84
题目主要信息：
- 序列化二叉树即找一种顺序存储二叉树的节点，并以相同的方式能够读取序列重新构建。
- 换种说法，就是遍历二叉树，记录每个节点，再以同样的方式遍历就可以还原二叉树。
- 遍历的方法有四种：前序遍历、中序遍历、后序遍历、层次遍历，理论上只要以相同的方式序列化或者反序列化，都可以解题。
举一反三：
学习完本题的思路你可以解决如下题目：
方法：前序遍历（推荐使用）
知识点：二叉树递归
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键。
而二叉树的递归，则是将某个节点的左子树、右子树看成一颗完整的树，那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题，因此可以自我调用函数不断进入子树。
思路：
序列化即将二叉树的节点值取出，放入一个字符串中，我们可以按照前序遍历的思路，遍历二叉树每个节点，并将节点值存储在字符串中，我们用‘#’表示空节点，用‘!'表示节点与节点之间的分割。
反序列化即根据给定的字符串，将二叉树重建，因为字符串中的顺序是前序遍历，因此我们重建的时候也是前序遍历，即可还原。
具体做法：
- step 1：优先处理序列化，首先空树直接返回“#”，然后调用SerializeFunction函数前序递归遍历二叉树。
SerializeFunction(root, res);
- step 2：SerializeFunction函数负责前序递归，根据“根左右”的访问次序，优先访问根节点，遇到空节点在字符串中添加‘#’，遇到非空节点，添加相应节点数字和‘!’，然后依次递归进入左子树，右子树。
//根节点
str.append(root.val).append('!');
//左子树
SerializeFunction(root.left, str);
//右子树
SerializeFunction(root.right, str);
- step 3：创建全局变量index表示序列中的下标（C++中直接指针完成）。
- step 4：再处理反序列化，读入字符串，如果字符串直接为"#"，就是空树，否则还是调用DeserializeFunction函数前序递归建树。
TreeNode res = DeserializeFunction(str);
- step 5：DeserializeFunction函数负责前序递归构建树，遇到‘#’则是空节点，遇到数字则根据感叹号分割，将字符串转换为数字后加入新创建的节点中，依据“根左右”，创建完根节点，然后依次递归进入左子树、右子树创建新节点。
TreeNode root = new TreeNode(val);
......
//反序列化与序列化一致，都是前序
root.left = DeserializeFunction(str);
root.right = DeserializeFunction(str);
图示：
Java实现代码：
import java.util.*;
public class Solution {
//序列的下标
public int index = 0;
//处理序列化的功能函数（递归）
private void SerializeFunction(TreeNode root, StringBuilder str){
//如果节点为空，表示左子节点或右子节点为空，用#表示
if(root == null){
str.append('#');
return;
}
//根节点
str.append(root.val).append('!');
//左子树
SerializeFunction(root.left, str);
//右子树
SerializeFunction(root.right, str);
}
public String Serialize(TreeNode root) {
//处理空树
if(root == null)
return "#";
StringBuilder res = new StringBuilder();
SerializeFunction(root, res);
//把str转换成char
return res.toString();
}
//处理反序列化的功能函数（递归）
private TreeNode DeserializeFunction(String str){
//到达叶节点时，构建完毕，返回继续构建父节点
//空节点
if(str.charAt(index) == '#'){
index++;
return null;
}
//数字转换
int val = 0;
//遇到分隔符或者结尾
while(str.charAt(index) != '!' && index != str.length()){
val = val * 10 + ((str.charAt(index)) - '0');
index++;
}
TreeNode root = new TreeNode(val);
//序列到底了，构建完成
if(index == str.length())
return root;
else
index++;
//反序列化与序列化一致，都是前序
root.left = DeserializeFunction(str);
root.right = DeserializeFunction(str);
return root;
}
public TreeNode Deserialize(String str) {
//空序列对应空树
if(str == "#")
return null;
TreeNode res = DeserializeFunction(str);
return res;
}
}
C++实现代码：
class Solution {
public:
//处理序列化的功能函数（递归）
void SerializeFunction(TreeNode* root, string& str){
//如果指针为空，表示左子节点或右子节点为空，用#表示
if(root == NULL){
str += '#';
return;
}
//根节点
string temp = to_string(root->val);
str += temp + '!';// 加!，区分节点
//左子树
SerializeFunction(root->left, str);
//右子树
SerializeFunction(root->right, str);
}
char* Serialize(TreeNode *root) {
//处理空树
if(root == NULL)
return "#";
string res;
SerializeFunction(root, res);
//把str转换成char
char* charRes = new char[res.length() + 1];
strcpy(charRes, res.c_str());
charRes[res.length()] = '\0';
return charRes;
}
//处理反序列化的功能函数（递归）
TreeNode* DeserializeFunction(char** str){
//到达叶节点时，构建完毕，返回继续构建父节点
//双**表示取值
if(**str == '#'){
(*str)++;
return NULL;
}
//数字转换
int val = 0;
while(**str != '!' && **str != '\0'){
val = val * 10 + ((**str) - '0');
(*str)++;
}
TreeNode* root = new TreeNode(val);
//序列到底了，构建完成
if(**str == '\0')
return root;
else
(*str)++;
//反序列化与序列化一致，都是前序
root->left = DeserializeFunction(str);
root->right = DeserializeFunction(str);
return root;
}
TreeNode* Deserialize(char *str) {
//空序列对应空树
if(str == "#"){
return NULL;
}
TreeNode* res = DeserializeFunction(&str);
return res;
}
};
Python代码实现：
import sys
#设置递归深度
sys.setrecursionlimit(100000)
class Solution:
def __init__(self):
self.index = 0
self.s = ""
#处理序列化（递归）
def SerializeFunction(self, root):
#空节点
if not root:
self.s += '#'
return
#根节点
self.s += (str)(root.val) + '!'
#左子树
self.SerializeFunction(root.left)
#右子树
self.SerializeFunction(root.right)
def Serialize(self, root):
if not root:
return '#'
self.s = ""
self.SerializeFunction(root)
return self.s
#处理反序列化的功能函数（递归）
def DeserializeFunction(self, s: str):
# 到达叶节点时，构建完毕，返回继续构建父节点
#空节点
if self.index >= len(s) or s[self.index] == "#":
self.index += 1
return None
# 数字转换
val = 0
#遇到分隔符或者结尾
while s[self.index] != '!' and self.index != len(s):
val = val * 10 + (int)(s[self.index])
self.index += 1
root = TreeNode(val)
#序列到底了，构建完成
if self.index == len(s):
return root
else:
self.index += 1
#反序列化与序列化一致，都是前序
root.left = self.DeserializeFunction(s)
root.right = self.DeserializeFunction(s)
return root
def Deserialize(self, s):
if s == "#":
return None
return self.DeserializeFunction(s)
复杂度分析：
- 时间复杂度：，其中为二叉树节点数，前序遍历，每个节点遍历一遍
- 空间复杂度：，最坏情况下，二叉树退化为链表，递归栈最大深度为
