描述
设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串， 并且可以将字符串反序列化为原来的树结构。
注意事项
There is no limit of how you deserialize or serialize a binary tree,
LintCode will take your output of serialize as the input of deserialize, it won't check the result of serialize.
样例
给出一个测试数据样例， 二叉树{3,9,20,#,#,15,7}，表示如下的树结构：
3
/ \
9 20
/ \
15 7
我们的数据是进行BFS遍历得到的。当你测试结果wrong answer时，你可以作为输入调试你的代码。你可以采用其他的方法进行序列化和反序列化。
关键点
- 要知道序列化是什么
//www.greatytc.com/writer#/notebooks/15589466/notes/16028033/preview- 无论是序列化还是反序列化都需要用queue来控制结点的执行顺序，当然queue的实现要根据题目需求选择是用LinkedList()方法还是ArrayList方法，本题算法中用到大量读取操作，若用LinkedList来实现queue不方便，本题用了ArrayList来实现queue
代码
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
class Solution {
// 加public表示全局类，该类可以import到任何类内
// 不加public默认为保留类，只能被同一个包内的其他类引用
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
public String serialize(TreeNode root) {
if (root == null) {
return "{}";
}
/* 利用for循环将树中结点全部添加到队列里面，利用队列来控制序列化顺序
* queue不是一个队列，是一个数组只是名字是queue
*/
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
queue.add(root);
for (int i = 0; i < queue.size(); i++) {
// queue是动态数组用get()方法来得到下标对应的数值
TreeNode node = queue.get(i);
// 空结点跳过不执行叶子结点添加的操作
if (node == null) {
continue;
}
// 无需理会叶子结点是不是空，把当前非空结点的叶子结点添加到了队列中
queue.add(node.left);
queue.add(node.right);
}
// 去掉队列结尾的空结点
while (queue.get(queue.size() - 1) == null) {
queue.remove(queue.size() - 1);
}
// 根据队列往动态数组里添加相应的值
// StringBuilder对象是动态对象，允许扩充它所封装的字符串中字符的数量
StringBuilder sb = new StringBuilder();
sb.append("{");
sb.append(queue.get(0).val);
// 在for循环前已经将初值加入sb中,所以 i 初值应设为1
for (int i = 1; i < queue.size(); i++) {
if (queue.get(i) == null) {
sb.append(",#");
}
else {
sb.append(",");
sb.append(queue.get(i).val);
}
}
sb.append("}");
return sb.toString();
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
public TreeNode deserialize(String data) {
// 字符用equals,数值用==
if (data.equals("{}")) {
return null;
}
// 此处需注意用点截取data的区间
// 字符串长度用length()
String[] vals = data.substring(1, data.length() - 1).split(",");
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
/* 新建一节点，节点值为vals[0]
* Integer.parseInt()将字符串转化为整型
*/
queue.add(root);
boolean isLeftChild = true;
// index是queue的索引
int index = 0;
// i 是vals的索引
for (int i = 1; i < vals.length; i++) {
// 数组长度用length
// 此处同样要注意先判断是不是空结点再讨论结点的子结点
if (!vals[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
if (isLeftChild) {
// 注意此处index=0，i=1
queue.get(index).left = node;
}
else {
queue.get(index).right = node;
}
queue.add(node);
/* '#'所的代表的空指针不要加入queue,没有任何意义，
* 此时for循环遍历的是index，即node的父节点，
* for循环接下来还要遍历node来确定node的子节点
* 此处不能忘记将node加入queue
*/
}
if (!isLeftChild) {
index++;
/* isLeftChild=false时说明此时index对应的结点的右儿子已经添加到队列中了，
* 应将index往后移一位
*/
}
// i 每变化一次 isLeftChild 进行一次变化
isLeftChild = !isLeftChild;
}
return root;
}
}
错误
- 单引号里面放一个字符，双引号里放多个字符
错误
错误代码
正确代码
需要先判断node是否为空，若node都为空研究node左右子结点无意义
