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)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return "[]";
List<TreeNode> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i =0; i < size;i++){
TreeNode node = queue.poll();
list.add(node);
if(node != null){
queue.offer(node.left);
queue.offer(node.right);
}
}
}
while(list.get(list.size()-1) ==null){
list.remove(list.size()-1);
}
StringBuilder builder = new StringBuilder();
builder.append("[");
builder.append(list.get(0).val);
for(int i = 1; i < list.size();i++){
builder.append(",");
if(list.get(i) == null){
builder.append("null");
}else{
builder.append(list.get(i).val);
}
}
builder.append("]");
return builder.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null || data.length() == 0 || data.equals("[]")){
return null;
}
data = data.substring(1,data.length()-1);
String[] strArr = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(strArr[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while(!queue.isEmpty() && i < strArr.length){
TreeNode node = queue.poll();
TreeNode left = null;
TreeNode right = null;
if(strArr[i].equals("null")){
node.left = null;
}else{
left = new TreeNode(Integer.parseInt(strArr[i]));
node.left = left;
queue.offer(left);
}
i++;
if( i >= strArr.length){
break;
}
if(strArr[i].equals("null")){
node.right = null;
}else{
right = new TreeNode(Integer.parseInt(strArr[i]));
node.right = right;
queue.offer(right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));Last updated