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.
/**
* 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) {
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Idea - 1
In the level order traversal of a full binary tree, each non-null node in a level would have exactly 2 children (can be null). Thus if we keep track of the null children in the serialization, we would be able to recreate the tree during deserialization. For an n-node tree, time and space complexity is
.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root==null)
{
return "null";
}
StringBuilder sb = new StringBuilder();
Deque<TreeNode> q = new ArrayDeque<>();
q.addLast(root);
sb.append(String.format("%s,", root.val));
while(!q.isEmpty())
{
TreeNode front = q.removeFirst();
String leftString = front.left==null ? "null" : String.valueOf(front.left.val);
sb.append(String.format("%s,", leftString));
if(front.left != null)
{
q.addLast(front.left);
}
String rightString = front.right==null ? "null" : String.valueOf(front.right.val);
sb.append(String.format("%s,", rightString));
if(front.right != null)
{
q.addLast(front.right);
}
}
String result = sb.toString();
// skip trailing comma
return result.substring(0, result.length()-1);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("null"))
{
return null;
}
String[] nodes = data.split(",");
int i = 0;
TreeNode root = new TreeNode(Integer.parseInt(nodes[i++]));
List<TreeNode> previousLevel = new ArrayList<>();
previousLevel.add(root);
while(!previousLevel.isEmpty())
{
List<TreeNode> currentLevel = new ArrayList<>();
for(TreeNode p : previousLevel)
{
String leftString = nodes[i++];
if(!leftString.equals("null"))
{
TreeNode leftChild = new TreeNode(Integer.parseInt(leftString));
p.left = leftChild;
currentLevel.add(leftChild);
}
String rightString = nodes[i++];
if(!rightString.equals("null"))
{
TreeNode rightChild = new TreeNode(Integer.parseInt(rightString));
p.right = rightChild;
currentLevel.add(rightChild);
}
}
previousLevel = currentLevel;
}
return root;
}
}
Runtime: 53 ms, faster than 17.30% of Java online submissions for Serialize and Deserialize Binary Tree.
Memory Usage: 46.8 MB, less than 5.05% of Java online submissions for Serialize and Deserialize Binary Tree.Idea - 2
We could use preorder traversal as well, complexity is similar.
public String serialize(TreeNode root) {
if(root==null)
{
return "null";
}
StringBuilder sb = new StringBuilder();
traversePreorder(root, sb);
String result = sb.toString();
return result.substring(0, result.length()-1);
}
private void traversePreorder(TreeNode x, StringBuilder sb)
{
if(x==null)
{
sb.append(String.format("null,"));
return;
}
sb.append(String.format("%s,", x.val));
traversePreorder(x.left, sb);
traversePreorder(x.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("null"))
{
return null;
}
String[] nodeStrings = data.split(",");
int[] I = {0};
return buildFromPreorder(nodeStrings, I);
}
private TreeNode buildFromPreorder(String[] nodeStrings, int[] I)
{
int i = I[0];
if(i >= nodeStrings.length || nodeStrings[i].equals("null"))
{
return null;
}
TreeNode x = new TreeNode( Integer.parseInt(nodeStrings[i]) );
++I[0];
x.left = buildFromPreorder(nodeStrings, I);
++I[0];
x.right = buildFromPreorder(nodeStrings, I);
return x;
}
}
Runtime: 44 ms, faster than 18.75% of Java online submissions for Serialize and Deserialize Binary Tree.
Memory Usage: 40.7 MB, less than 41.81% of Java online submissions for Serialize and Deserialize Binary Tree.
programmingpuzzles 