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.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
sb.append(NULL).append(SPLITER);
} else {
sb.append(root.val).append(SPLITER);
sb.append(serialize(root.left));
sb.append(serialize(root.right));
}
return sb.toString();
}
int i = -1;
private TreeNode dfs(String[] subs) {
i++;
if (subs[i].equals(NULL)) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
node.left = dfs(subs);
node.right = dfs(subs);
return node;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
return dfs(subs);
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
sb.append(NULL);
} else {
sb.append(node.val);
stack.push(node.right);
stack.push(node.left);
}
sb.append(SPLITER);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
if (subs[0].equals(NULL)) {
return null;
}
//System.out.println(data);
Stack<TreeNode> stack = new Stack<>();
TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
TreeNode cur = root;
stack.push(root);
for (int i = 1; i < subs.length; i++) {
if (!subs[i].equals(NULL)) {
TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
if (subs[i - 1].equals(NULL)) {
cur.right = node;
cur = cur.right;
stack.push(cur);
} else {
cur.left = node;
cur = cur.left;
stack.push(cur);
}
} else if (!stack.isEmpty()) {
cur = stack.pop();
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
sb.append(NULL);
} else {
sb.append(node.val);
stack.push(node.right);
stack.push(node.left);
}
sb.append(SPLITER);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
if (subs[0].equals(NULL)) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> meta = new Stack<>();
TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
Map<TreeNode, Integer> map = new HashMap<>();
stack.push(root);
for (int i = 1; i < subs.length; i++) {
while (!stack.isEmpty() && map.containsKey(stack.peek()) && map.get(stack.peek()) == 2) {
stack.pop();
}
TreeNode cur = stack.peek();
if (!subs[i].equals(NULL)) {
TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
if (map.containsKey(cur) && map.get(cur) == 1) {
cur.right = node;
stack.push(node);
} else {
cur.left = node;
stack.push(node);
}
}
map.put(cur, map.getOrDefault(cur, 0) + 1);
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Ver. 4
BFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append(NULL);
} else {
sb.append(node.val);
queue.offer(node.left);
queue.offer(node.right);
}
sb.append(SPLITER);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
if (subs[0].equals(NULL)) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
queue.offer(root);
int i = 1;
while (i < subs.length) {
TreeNode node = queue.poll();
if (!subs[i].equals(NULL)) {
node.left = new TreeNode(Integer.parseInt(subs[i]));
queue.offer(node.left);
}
i++;
if (!subs[i].equals(NULL)) {
node.right = new TreeNode(Integer.parseInt(subs[i]));
queue.offer(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));