题目描述
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
例如，可以根据层序遍历并特定标志空结点的方案序列化，也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。
假如一棵树共有 2 个结点， 其根结点为 1 ，根结点右子结点为 2 ，没有其他结点。按照上面第一种说法可以序列化为“1,#,2,#,#”，按照上面第二种说法可以序列化为“{0:1,2:2}”，按照上面第三种说法可以序列化为“1,2;2,1”，这三种序列化的结果都包含足以构建一棵与原二叉树完全相同的二叉树的信息。
示例1
输入：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}
题目分析
序列化方式可以使用题目提示的三种，其中使用 # 来标记空节点的方式较为简单：
在获取序列化字符串时，可以遍历树结点，当遇到非空结点，加入结点值，遇到空节点，加入 #；
在反序列化过程中，可以根据序列化字符串，非空节点创建相应的结点，递归赋值结点的子节点。
解题思路
方法1：深度遍历进行序列化和反序列化
使用深度遍历dfs的思路为：
序列化：
1.首先判断root为空，则返回"#,"；
2.当root不为空，使用StringBuilder sb加上当前的 root.val+",";
3.继续遍历 root.left 和 root.right，将子节点的序列化结果添加到 父节点的字符串中；
反序列化：
1.序列化的字符串，可以以“,”进行划分使用split()，生成对应的结点值的字符串数组nodes；
2.使用全局变量index，标记当前记录到的结点位置（数组下标）；
3.当 nodes[index]不为"#"空节点，则可以使用该值创建新的结点，并且继续初始化它的左右子节点，index每递归一次都加1，直到遍历完所有的结点；
方法2：广度遍历进行序列化和反序列化
使用广度遍历bfs的思路为：
序列化：
1.借用队列进行广度遍历，基本框架如下
bfs(root){
queue.offer(root);
while(!queue.isEmpty()){
TreeNode tmp = queue.poll();
if(tmp.left != null){ queue.offer(tmp.left);}
if(tmp.right!= null){ queue.offer(tmp.right);}
}
}2.层次遍历的序列化结果是按照每层的结点顺序加相应值，这里需要注意的是，使用“#”来表示空节点，则放入队列中的结点可以为null值，在它不为空的情况下再将左右子结点入队列；
3.这样一直遍历，直到队列中数据为空；
反序列化：
1.序列化的字符串，可以以“,”进行划分使用split()，生成对应的结点值的字符串数组nodes；
2.在广度遍历结点的情况下，同样需要队列来存储结点，先根据nodes[0]创建根节点，将根节点存入队列中；
3.每次从队列中取出nodes结点时，可以知道不管它的左右子节点是否为空（都有两个），后面的数组下标 i和i+1,就是当前结点的左右子节点，将不为空的结点继续放入队列，等待赋予它的左右子节点，对于结点数组来说，每次需要隔两个下标进行下一个结点的左右子节点赋值；
代码实现
方法1：深度遍历进行序列化和反序列化
String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
// 当结点为空时，使用 # 标记
if(root == null){
sb.append("#,");
return sb.toString();
}
// 先序遍历，存储结点信息
// 访问根节点
sb.append(root.val+",");
// 访问左子节点
sb.append(Serialize(root.left));
// 访问右子节点
sb.append(Serialize(root.right));
// 返回遍历结果
return sb.toString();
}
// 标记访问的结点下标
public int index = -1;
// str中包含的结点数组
public String[] nodes = null;
TreeNode Deserialize(String str) {
if(index == -1){
// 最开始的时候初始化数组
nodes = str.split(",");
}
// 访问下标加1
index++;
if(index >= nodes.length || nodes[index].equals("#")){
// 当超过数组长度，或者为空结点时，返回null
return null;
}
// 创建根结点
TreeNode root = new TreeNode(Integer.parseInt(nodes[index]));
// 获取左节点
root.left = Deserialize(str);
// 获取右节点
root.right = Deserialize(str);
return root;
}时间复杂度：O(n)，在递归过程中需要遍历树的所有结点；
空间复杂度：O(n)，在方法中使用了常量个数的变量，空间复杂度看递归深度，当树退化成链表时，递归深度最大，为树结点的数量n。
方法2：广度遍历进行序列化和反序列化
String Serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
// 借用队列进行层序遍历
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
// 从队列头部中取出元素
TreeNode node = que.poll();
if(node == null){
// 为空结点时，使用#标记
sb.append("#,");
}else{
// 不为空节点，需要记录值，且不管左右子节点是否为空，都放入队列中
sb.append(node.val + ",");
que.offer(node.left);
que.offer(node.right);
}
}
return sb.toString();
}
TreeNode Deserialize(String str) {
if(str == null || str.length() == 0 || str.charAt(0) == '#') return null;
// str中包含的结点数组
String[] nodes = str.split(",");
// 创建根节点
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
for(int i=1;i<nodes.length-1;i+=2){
// 从队列中取出根节点
TreeNode tmp = que.poll();
// 确定根节点的左右子节点
String l = nodes[i];
String r = nodes[i+1];
if(!l.equals("#")){
// 子节点不为空，则创建新的子节点，并且加入到队列中，以便继续添加其子节点
tmp.left = new TreeNode(Integer.parseInt(l));
que.offer(tmp.left);
}
if(!r.equals("#")){
tmp.right = new TreeNode(Integer.parseInt(r));
que.offer(tmp.right);
}
}
return root;
}时间复杂度：O(n)，在遍历过程中，需要遍历树的所有结点；
空间复杂度：O(n)，借助队列来存储结点，当出栈一个结点时，最多需要入栈两个结点，队列存储结点的最大值为 n/2，空间复杂度为O(n)。
京公网安备 11010502036488号