LintCode 7.Serialize and Deserialize Binary Tree（含测试代码）
题目描述
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
样例
给出一个测试数据样例， 二叉树{3,9,20,#,#,15,7}，表示如下的树结构：
我们的数据是进行BFS遍历得到的。当你测试结果wrong answer时，你可以作为输入调试你的代码。你可以采用其他的方法进行序列化和反序列化。
在编程过程中，采用Queue队列结构来保存树节点，因此有必要熟悉一下Queue接口（Deque接口是Queue接口的子接口，代表一个双端队列）的相关知识点。
1.Queue接口与List、Set属于同一级别，都是继承了Collection接口。LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
2.Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，而add()和remove()方法在失败的时候会抛出异常。
另外要用到字符串结构，需弄明白 String, StringBuilder 以及 StringBuffer 这三个类之间有什么区别？
1.首先说运行速度，或者说是执行速度，在这方面运行速度快慢为：StringBuilder > StringBuffer > String
String最慢的原因：
String为字符串常量，而StringBuilder和StringBuffer均为字符串变量，即String对象一旦创建之后该对象是不可更改的，但后两者的对象是变量，是可以更改的。
2. 再来说线程安全
在线程安全上，StringBuilder是线程不安全的，而StringBuffer是线程安全的。
因此：
String：适用于少量的字符串操作的情况
StringBuilder：适用于单线程下在字符缓冲区进行大量操作的情况
StringBuffer：适用多线程下在字符缓冲区进行大量操作的情况
实现代码：
1 import java.util.LinkedList;
2 import java.util.Queue;
3
4 class TreeNode {
5 public int val;//节点的值
6 public TreeNode left,right;//左右节点
7 public TreeNode(int val){
8 this.val = val;//初始化节点
9 this.left = this.right = null;
10 }
11 }
12
13 public class SerializeTree {
14 public static void main(String[] args) throws Exception {
15 TreeNode node1 = new TreeNode(3);
16 TreeNode node2 = new TreeNode(9);
17 TreeNode node3 = new TreeNode(20);
18 node1.left = node2;
19 node1.right = node3;
20 TreeNode node4 = new TreeNode(15);
21 TreeNode node5 = new TreeNode(7);
22 node3.left = node4;
23 node3.right = node5;
24
25 String s = new SerializeTree().serialize(node1);
26 System.out.println(s);
27
28 String str = new String("3,9,20,#,#,15,7");
29 //TreeNode root = new SerializeTree().deserialize(s);
30 TreeNode root = new SerializeTree().deserialize(str);
31 System.out.println((int)root.val);
32 System.out.println(root.left.val);
33 System.out.println(root.right.val);
34
35
36 }
37
38 /*将一棵树序列化一个字符串*/
39 public String serialize(TreeNode root) {
40 Queue<TreeNode> queue = new LinkedList<>();
41 StringBuffer sb = new StringBuffer();
42
43 queue.offer(root);
44 while(!queue.isEmpty()) {
45 TreeNode data = queue.poll();
46 if(data != null) {
47 sb.append(data.val+",");
48 queue.offer(data.left);
49 queue.offer(data.right);
50 }
51 else
52 sb.append("#,");
53 }
54 //return sb.toString();
55 return sb.substring(0, sb.length()-1);//去掉字符串末尾的“，”号
56 }
57
58 /*将一个字符串反序列化为一棵树*/
59 public TreeNode deserialize(String data) throws Exception {
60 Queue<TreeNode> queue = new LinkedList<>();
61 String string = data.substring(0, data.length());
62 String[] s = string.split(",");
63 /*for(int i =0;i<s.length-1;i++) {
64 System.out.print(s[i]+" ");
65 }
66 System.out.println(s[s.length-1]);*/
67 int i = 0;
68 if(s[i].equals("#"))
69 return null;
70
71 TreeNode root = new TreeNode(Integer.parseInt(s[i]));
72 queue.offer(root);
73
74 while(!queue.isEmpty() && i < s.length-1 ) {
75 i++;
76 TreeNode tmp = queue.poll();
77
78 if(s[i].equals("#")) {
79
80 tmp.left = null;
81 }
82 else
83 {
84 TreeNode left = new TreeNode(Integer.parseInt(s[i]));
85 tmp.left = left;
86 queue.offer(left);
87 }
88
89 i++;
90 if(s[i].equals("#"))
91 tmp.right = null;
92 else
93 {
94 TreeNode right = new TreeNode(Integer.parseInt(s[i]));
95 tmp.right = right;
96 queue.offer(right);
97 }
98 }
99 return root;
100 }
101
102 }