Problem:
Given a Binary Tree (not binary search tree, the node value don't follow particular rule). Convert the tree to a string (serialize), then convert the string back to a tree with the original structure (deserialize).
Example:
Given a tree:
2
/ \
9 4
/ / \
1 7 5
you can serialize the tree to string
for example, "[2,9,1,null,null,null,4,7,null,null,5,null,null]" then manage to deserialize the string back to
2
/ \
9 4
/ / \
1 7 5
Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Solution:
At first glance, we could attempt to use preorder or post order sequence as the serialized string. However this problem is not the same as BST Serialize and Deserialize. In another words, we can not use the node value to figure out the left subtree and right subtree division. Besides the node values, we need extra information in the serialized string for the binary tree structure.
One working approach could print out 2 sequences, for example, inorder and preorder arrays. Then we can deserialize as in Construct Binary Tree from Preorder and Inorder Traversal problem or Construct Binary Tree from Postorder and Inorder Traversal problem.
Let's look at a different approach, if we have the preorder sequence with nulls explicitly prints out, are we able to deserialize? We know the first array element is the root node, then the next node is also a root node. The next element is either null or a value. If it is null, we know, the left subtree is null, the rest of the subarray is right substree. If the next element is a value, we can recursively argue, the element 1 step right is also a root. We can recursively pass in the subarray on the right. The exit condition is array element is null.
This approach is better because
import java.util.*;
class Solution {
public static void main(String...args) {
Node root = new Node(7,
new Node(4, null, new Node(5, null, null)),
new Node(9, new Node(8, null, null), null)
);
StringBuilder sb = new StringBuilder();
serialize(root, sb);
System.out.println(sb.toString());
root = deserialize(sb.toString());
//verify result
sb = new StringBuilder();
serialize(root, sb);
System.out.println(sb.toString());
}
private static void serialize(Node root, StringBuilder sb) {
if(root == null) {
sb.append("null,");
return;
}
sb.append(root.value + ",");
serialize(root.left, sb);
serialize(root.right, sb);
}
private static Node deserialize(String str) {
String[] a = str.split(",");
List<String> list = new ArrayList<>(Arrays.asList(a));
return rdeserialize(list);
}
private static Node rdeserialize(List<String> list) {
if(list.size() <= 0) return null;
String val = list.get(0);
list.remove(0);
if(val.equals("null")) return null;
Node root = new Node(Integer.parseInt(val), null, null);
root.left = rdeserialize(list);
root.right = rdeserialize(list);
return root;
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
class Solution {
public static void main(String...args) {
Node root = new Node(7,
new Node(4, null, new Node(5, null, null)),
new Node(9, new Node(8, null, null), null)
);
StringBuilder sb = new StringBuilder();
serialize(root, sb);
System.out.println(sb.toString());
root = deserialize(sb.toString());
//verify result
sb = new StringBuilder();
serialize(root, sb);
System.out.println(sb.toString());
}
private static void serialize(Node root, StringBuilder sb) {
if(root == null) {
sb.append("null,");
return;
}
sb.append(root.value + ",");
serialize(root.left, sb);
serialize(root.right, sb);
}
private static Node deserialize(String str) {
String[] a = str.split(",");
List<String> list = new ArrayList<>(Arrays.asList(a));
return rdeserialize(list);
}
private static Node rdeserialize(List<String> list) {
if(list.size() <= 0) return null;
String val = list.get(0);
list.remove(0);
if(val.equals("null")) return null;
Node root = new Node(Integer.parseInt(val), null, null);
root.left = rdeserialize(list);
root.right = rdeserialize(list);
return root;
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
The time complexity is O(N), we process each array element once. The space complexity is O(N), the space we used to store the node array is O(N).
