-
Notifications
You must be signed in to change notification settings - Fork 7
/
SerializeAndDeserializeBinaryTree.java
61 lines (49 loc) · 2.54 KB
/
SerializeAndDeserializeBinaryTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//Design an algorithm to serialize and deserialize a binary search tree.
//There is no restriction on how your serialization/deserialization algorithm should work.
//You just 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.
//Intuiton, use BFS/DFS
//TO SERIALIZE, USE PREORDER TRAVERSAL aka root-left-right, and put the tree into a STRING!!
//TO DESERIALIZE, use a queue and do bfs traversal
//TC: O(N) to serialize and deseralze by going through all of the tree, N is number of nodes in tree
//SC: O(N) to store the tree as a string
https://leetcode.com/problems/serialize-and-deserialize-bst/discuss/177617/the-General-Solution-for-Serialize-and-Deserialize-BST-and-Serialize-and-Deserialize-BT
NOTE, difference between this one and serialze BST is that we have to use "NULL" to check whether to
add null, rather than the BST property!
//TC: O(N) for both serialize/deserialize, where n is number of nodes, because we visit them all
//SC: O(N) for recusrive stack, for both serialize/deserialize, in worst case with unbalanced tree
public class Codec {
private static final String SPLITER = ",";
private static final String NULL = "N";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder st = new StringBuilder();
serialize(root, st);
return st.toString();
}
public void serialize(TreeNode root, StringBuilder st) {
if (root == null) st.append(NULL + SPLITER);
else {
st.append(root.val + SPLITER); //need to add the node we are on to answer!
serialize(root.left, st); //then recursively call this function onto the left and right subtree
serialize(root.right, st);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> queue = new LinkedList<>(); //need to use a Queue because we need to derailzie in order
queue.addAll(Arrays.asList(data.split(SPLITER))); //populate queue
return deseralize(queue);
}
public TreeNode deseralize(Queue<String> queue) {
String cur = queue.poll();
if (cur.equals(NULL)) return null;
TreeNode root = new TreeNode(Integer.parseInt(cur));
root.left = deseralize(queue);
root.right = deseralize(queue);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));