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
         
           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
          
            queue = new LinkedList<>(); 61         String string = data.substring(0, data.length()); 62         String[] s = string.split(","); 63         /*for(int i =0;i

题目描述

样例