题目
请实现两个函数，分别用来序列化和反序列化二叉树
分析
要确定一颗二叉树，可以用前序遍历和中序遍历唯一确定，因此可以把一颗二叉树序列化成前序和中序遍历，反序列化时，根据前序和中序重构。
但是，这有两个缺点：
（1）二叉树不能有数值相同的节点；
（2）必须将二叉树全部读入内存才能进行反序列化。
我们可以从根节点开始遍历，反序列化在根节点读出来之前就可以开始。这样就不用全部读入内存，因此我们可以利用前序遍历确定二叉树，前序遍历是“根-左-右”， 遇到空节点时，赋值为特殊字符，反序列化时，就利用特殊字符进行这些特殊字符确定节点。
举例说明：
图中二叉树的遍历顺序是：
1，2，4，#，#，#，3，5，#，#，6，#，#
如何反序列化呢？
首先读出根节点1，然后读出2，是1的左子树，接着4是2的左子树，#表示4的左孩子是空。下一个#表示4的右孩子也是空，接下来回到节点2，第三个#表示2的右孩子是空。
以此类推。
代码
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
int index = -1;
// 前序遍历
String Serialize(TreeNode root) {
StringBuffer buffer = new StringBuffer();
if (root == null) {
buffer.append("#,");
return buffer.toString();
}
buffer.append(root.val +",");
// 递归的前序遍历
buffer.append(Serialize(root.left));
buffer.append(Serialize(root.right));
return buffer.toString();
}
TreeNode Deserialize(String str) {
index ++;
// 字符串转化为数组
String [] strings = str.split(",");
TreeNode temp = null;
if (!strings[index].equals("#")) {
temp = new TreeNode(Integer.valueOf(strings[index]));
temp.left = Deserialize(str);
temp.right = Deserialize(str);
}
return temp;
}
}
