Serialize and Deserialize Binary Tree
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Example:
You may serialize the following tree:
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]"Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
之前做的
第一遍自己做的，runtime很长，有很多坑 1. serialize时 两端的[ ]，加密完以后最后的null 要去掉 2. deserialize split 数组，index问题，注意别越界
/**
* 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;
* }
* }
*/
public 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
String res = "{";
if(root == null)
return "{}";
List<TreeNode> treeList = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
treeList.add(node);
if(node != null){
queue.offer(node.left);
queue.offer(node.right);
}
}
while(treeList.get(treeList.size()-1) == null){
treeList.remove(treeList.size()-1);
}
res += treeList.get(0).val;
for(int i = 1; i < treeList.size();i++){
if(treeList.get(i) == null){
res += ",#";
}else{
res += ",";
res += treeList.get(i).val;
}
}
res += "}";
System.out.println(res);
return res;
}
/**
* 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.equals("{}")){
return null;
}
data = data.substring(1,data.length()-1);
String[] s= data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(s[0]));
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int index = 1;
while(!q.isEmpty() && index < s.length){
TreeNode node = q.poll();
if(node == null){
continue;
}
TreeNode left = null;
TreeNode right = null;
if(index < s.length && !s[index].equals("#")){
left = new TreeNode(Integer.parseInt(s[index++]));
}else{
index++;
}
if(index < s.length && !s[index].equals("#")){
right = new TreeNode(Integer.parseInt(s[index++]));
}else{
index++;
}
if(node != null){
node.left = left;
node.right = right;
q.offer(node.left);
q.offer(node.right);
}
}
return root;
}
}三刷版本 2个坑，加密时，node为null时 left和right 报异常，解密时while循环内保证i不越界
时间复杂度 和空间复杂度 o(n)
Last updated