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.
For example, you may serialize the following tree
1
/ \
2 3
/ \
4 5
Answer:
Method: Preorder and DFS!
public class Codec {
private StringBuilder sb = new StringBuilder();
private int index = 0;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
index = 0;
serialize(root, sb);
return sb.toString();
}
public void serialize(TreeNode root, StringBuilder sb){
//preorder and using '# ' for null node!
if(root==null){
sb.append("#,");
return;
}
sb.append(root.val + ",");
serialize(root.left, sb);
serialize(root.right, sb);
return;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data==null || data.length()==0){
return null;
}
String[] strArr = data.split(",");
return deserialize(strArr);
}
public TreeNode deserialize(String[] str){
if(index >= str.length){
return null;
}
String str_val = str[index];
if(str_val.equals("#")){
index++;
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(str_val));
index++;
root.left = deserialize(str);
root.right = deserialize(str);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
