7. 二叉树的序列化和反序列化

题目链接：

https://www.lintcode.com/problem/serialize-and-deserialize-binary-tree/description

设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。

如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。

Example

样例 1：

输入：{3,9,20,#,#,15,7} 输出：{3,9,20,#,#,15,7} 解释： 二叉树 {3,9,20,#,#,15,7}，表示如下的树结构： 3 / \ 9 20 / \ 15 7 它将被序列化为 {3,9,20,#,#,15,7}

样例 2：

输入：{1,2,3} 输出：{1,2,3} 解释： 二叉树 {1,2,3}，表示如下的树结构： 1 / \ 2 3 它将被序列化为 {1,2,3}

我们的数据是进行 BFS 遍历得到的。当你测试结果 Wrong Answer 时，你可以作为输入调试你的代码。

你可以采用其他的方法进行序列化和反序列化。

Notice

对二进制树进行反序列化或序列化的方式没有限制，LintCode 将您的 serialize输出作为 deserialize 的输入，它不会检查序列化的结果。

思路：

1、序列化：首先确定树中有多少结点size，然后用队列层次遍历。当结点为空（null）时，则左右结点都为null入队。

                   每当出队一个非空结点时，size--;

2、反序列化：将字符串去掉前后的大括号"{}"（subString(1,data.length()-1)）;然后再转化为字符串数组

                       将字符串数组转化为树。遍历字符串数组，当前i个字符串为"#",则对应的结点为null。