Problem:
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
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ 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.
Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.
Solution:
BFS
/**
* 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 "[]";
Queue<TreeNode> q = new LinkedList<TreeNode>();
ArrayList<String> result = new ArrayList<String>();
q.offer(root);
TreeNode rightMost = root;
int maxDepth = maxDepth(root, 0);
int depth = 1;
while (!q.isEmpty()) {
TreeNode current = q.poll();
if (current == null) {
if (depth <= maxDepth) {
result.add("null");
}
continue;
}
result.add(current.val + "");
q.offer(current.left);
q.offer(current.right);
if (current == rightMost) {
depth++;
rightMost = current.right == null ? current.left : current.right;
}
}
return result.toString();
}
private int maxDepth(TreeNode root, int current) {
if (root == null) return current;
return Math.max(maxDepth(root.left, current + 1), maxDepth(root.right, current + 1));
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length() < 2) return null;
data = data.substring(1, data.length() - 1);
if (data.equals("")) return null;
String[] elements = data.split(", ");
TreeNode root = new TreeNode(Integer.parseInt(elements[0]));
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
int index = 1;
while (!q.isEmpty()) {
TreeNode current = q.poll();
if (current == null || index >= elements.length) continue;
String e = elements[index];
String t = index + 1 >= elements.length ? "null" : elements[index + 1];
current.left = e.equals("null") ? null : new TreeNode(Integer.parseInt(e));
current.right = t.equals("null") ? null : new TreeNode(Integer.parseInt(t));
index += 2;
q.offer(current.left);
q.offer(current.right);
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));