二叉树的序列化和反序列化。我一开始想用BFS的，但第一不知道怎么处理空子树，第二不知道怎么还原一棵树。于是照着solutions的高票答案写了一遍。
Approach 1 : preorder traverse（dfs）
1
/ \
2 3
/ \
4 5
对于上面这棵树，这种方法会把它serialize成"1,2,X,X,3,4,X,X,5,X,X,"这样的字符串。也就是preorder地遍历。buildTree的过程也是递归，跟serialize的过程其实就是相反的。递归构造一棵树的方法还是值得注意的。
private static final String spliter = ",";
private static final String NN = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
preorder(root, sb);
return sb.toString();
}
private void preorder(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
return;
}
sb.append(node.val).append(spliter);
preorder(node.left, sb);
preorder(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>();
queue.addAll(Arrays.asList(data.split(spliter)));
//如何返回root：递归返回的最终就是root
return buildTree(queue);
}
private TreeNode buildTree(Queue<String> queue) {
String val = queue.poll();
if (val.equals(NN)) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(queue);
node.right = buildTree(queue);
return node;
}
问了同举，他让我用Gson.toJson试一下。
Approach 2 : BFS
我先去看电影了。
bfs的解法会把上面的tree序列化成："1 2 3 n n 4 5 n n n n "这样。理解起来其实更容易。serialize的过程就是level order traverse的过程，注意null的处理。build tree的过程是把null跳过不接到parent上。
//BFS
public String serialize(TreeNode root) {
if (root == null) return "";
Queue<TreeNode> q = new LinkedList<>();
StringBuilder res = new StringBuilder();
q.add(root);
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) {
res.append("n ");
continue;
}
res.append(node.val + " ");
q.add(node.left);
q.add(node.right);
}
return res.toString();
}
public TreeNode deserialize(String data) {
if (data == "") return null;
Queue<TreeNode> q = new LinkedList<>();
String[] values = data.split(" ");
TreeNode root = new TreeNode(Integer.parseInt(values[0]));
q.add(root);
for (int i = 1; i < values.length; i++) {
TreeNode parent = q.poll();
if (!values[i].equals("n")) {
TreeNode left = new TreeNode(Integer.parseInt(values[i]));
parent.left = left;
q.add(left);
}
if (!values[++i].equals("n")) {
TreeNode right = new TreeNode(Integer.parseInt(values[i]));
parent.right = right;
q.add(right);
}
}
return root;
}
摘抄：
【注意】
1、不要幻想不用分隔符（我用的是“，”），没有分隔符对于1位以上的数是区分不了的。比如345，你觉得是1个数345还是分别3个数呢？（这就是我愚蠢的地方，耗费我数小时思考）
2、String的split方法有个坑：
对于"11,12,13,"，用data.split(",")可以得到正确结果；但是",11,12,13"split后得到的是null。所以分隔符要放后面
这题还有个follow up:449. Serialize and Deserialize BST ,用这题的代码也可以过，但是没用到BST的性质。看了下那题的答案，不是很懂deserialization的过程。
ref：
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/#/solutions
http://www.jianshu.com/p/18578f767668
http://blog.csdn.net/byamao1/article/details/53086548
