Serialize and Deserialize
设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的,你只需要确保可以将二叉树序列化为一个字符串,并且可以将字符串反序列化为原来的树结构。
样例
给出一个测试数据样例, 二叉树{3,9,20,#,#,15,7},表示如下的树结构:
3
/ \
9 20
/ \
15 7
我们的数据是进行BFS遍历得到的。当你测试结果wrong answer时,你可以作为输入调试你的代码。
你可以采用其他的方法进行序列化和反序列化。
Solution
Serialize
- 注意这个是Lintcode的Serialize, 和Leetcode的区别在于他使用的是BFS. 而后者则是使用的pre-order DFS.
- null object 和 null的区别.
- flag的设计: 要有初始值, 在进入循环的时候update, 对于每一个节点再次update. 那么当这一层结束后就是有效的flag.
De-serialize
- 还是使用BFS解决. 和Pre-order的de-serialize一样, 和各自的Serialize有一个一一对应的关系.
- 第一次写的时候出现idx超出array size的问题. 这是为什么呢? 因为我在判断token[idx]的时候居然判断了4次. 因为每一次判断都要idx++. 然后我把4个if并成2个if…else就OK了.
- 注意这个时候的while loop判断不是parents queue是否为空, 而是判断token[] array走完没有. 我一开始这里搞错了, 居然去判断string走完没有. 注意string就是char Array. 例如{3, 9, 20, #, #, 15, 7}, 这个string的length是21. 而token[]则是7.
- 还有注意这里update parents queue的时候要注意. 这里的做法是对于”#”, 则不加入null到queue. 不然queue的size()就不对了. 因为这里不用traverse null node.
/**
* 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 {
/**
* 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) {
StringBuffer buffer = new StringBuffer();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root != null){
queue.offer(root);
buffer.append(root.val);
}
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
if(node.left == null){
buffer.append(",#");
} else {
buffer.append(","+node.left.val);
queue.offer(node.left);
}
if(node.right == null){
buffer.append(",#");
} else {
buffer.append(","+node.right.val);
queue.offer(node.right);
}
}
}
return buffer.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) {
if(data == null || data.length() == 0) return null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
String[] arr = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
queue.offer(root);
for(int i = 1; i < arr.length; i++){
TreeNode left = null, right = null;
if(!arr[i].equals("#")){
left = new TreeNode(Integer.parseInt(arr[i]));
}
if(++i < data.length() && !arr[i].equals("#")){
right = new TreeNode(Integer.parseInt(arr[i]));
}
TreeNode parent = queue.poll();
parent.left = left;
parent.right = right;
if(left != null)
queue.offer(left);
if(right != null)
queue.offer(right);
}
return root;
}
}