Amazon
Amazon
Amazon
ByteDance
ByteDance
2020-10-11
449. Serialize and Deserialize BST
Question:
Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Example 1:
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. 0 <= Node.val <= 104- The input tree is guaranteed to be a binary search tree.
Solution:
Using preorder to serialize the tree and use queue to seperate the string into two parts: larger than root and smaller than root.
/**
* 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) {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(TreeNode root, StringBuilder sb){
if (root == null) return;
sb.append(root.val + " ");
serializeHelper(root.left, sb);
serializeHelper(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) return null;
Queue<Integer> que = new LinkedList<>();
for (String str: data.split(" ")) {
que.offer(Integer.valueOf(str));
}
return deserializeHelper(que);
}
private TreeNode deserializeHelper(Queue<Integer> que) {
if (que.size() == 0) return null;
int curr = que.poll();
TreeNode root = new TreeNode(curr);
Queue<Integer> smallerQue = new LinkedList<>();
while (!que.isEmpty() && que.peek() < curr) {
smallerQue.add(que.poll());
}
root.left = deserializeHelper(smallerQue);
root.right = deserializeHelper(que);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;
Also can be solved by using the boundary checking:
/**
* 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) {
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(TreeNode root, StringBuilder sb){
if (root == null) return;
sb.append(root.val + " ");
serializeHelper(root.left, sb);
serializeHelper(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) return null;
String[] arr = data.split(" ");
return deserializeHelper(arr, 0, arr.length - 1);
}
private TreeNode deserializeHelper(String[] arr, int low, int high) {
if (low > high) return null;
// System.out.println(low + 1 + " " + high);
TreeNode root = new TreeNode(Integer.valueOf(arr[low]));
int i = low + 1;
for(; i <= high; i++) {
if (Integer.valueOf(arr[i]) > Integer.valueOf(arr[low])) break;
}
root.left = deserializeHelper(arr, low + 1, i - 1);
root.right= deserializeHelper(arr, i, high);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;
Using BFS to encode the TreeNode, and use queue to remember the next available node.
/**
* 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 "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
TreeNode curr = que.poll();
if (curr == null) {
sb.append(",#");
} else {
sb.append("," + curr.val);
que.offer(curr.left);
que.offer(curr.right);
}
}
return sb.substring(1);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0 || data.equals("#")) {
return null;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
String[] strs = data.split(",");
TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
que.offer(root);
for (int i = 1; i < strs.length; i++) {
if (strs[i].equals("#")) {
que.offer(null);
if (i%2 != 0){
while(que.peek() == null) que.poll();
que.peek().left = null;
}
else que.poll().right = null;
} else {
TreeNode curr = new TreeNode(Integer.valueOf(strs[i]));
que.offer(curr);
if (i%2 != 0){
while(que.peek() == null) que.poll();
que.peek().left = curr;
}
else que.poll().right = curr;
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;