设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。
如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。
/**
* 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) {
// write your code here
Queue queue = new LinkedList();
queue.offer(root);
StringBuilder builder = new StringBuilder();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
if(null == node){
builder.append("#,");
}else{
builder.append(node.val+",");
queue.offer(node.left);
queue.offer(node.right);
}
}
return builder.toString().substring(0,builder.length()-1);
}
/**
* 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) {
// write your code here
if(data == null || "#".equals(data))
return null ;
String [] dataArray = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(dataArray[0]+""));
Queue queue = new LinkedList();
queue.offer(root);
for(int i = 1; i< dataArray.length; i = i+2){
String left = dataArray[i];
String right =dataArray[i+1];
TreeNode leftNode = ("#".equals(left) ? null :new TreeNode(Integer.parseInt(dataArray[i]+"")) );
TreeNode rightNode = ("#".equals(right) ? null :new TreeNode(Integer.parseInt(dataArray[i+1]+"")) );
TreeNode temp = queue.poll();
temp.left = leftNode;
temp.right = rightNode;
if(leftNode != null){
queue.offer(leftNode);
}
if(rightNode !=null){
queue.offer(rightNode);
}
}
return root;
}
}
网友评论