Serialize And Deserialize BST Problem
Description
LeetCode Problem 449.
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:
1
2
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
1
2
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range [0, 10^4].
- 0 <= Node.val <= 10^4
- The input tree is guaranteed to be a binary search tree.
Sample C++ Code
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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string order;
inorderDFS(root, order);
return order;
}
inline void inorderDFS(TreeNode* root, string& order) {
if (!root) return;
char buf[4];
memcpy(buf, &(root->val), sizeof(int)); //burn the int into 4 chars
for (int i=0; i<4; i++) order.push_back(buf[i]);
inorderDFS(root->left, order);
inorderDFS(root->right, order);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int pos = 0;
return reconstruct(data, pos, INT_MIN, INT_MAX);
}
inline TreeNode* reconstruct(const string& buffer, int& pos, int minValue, int maxValue) {
if (pos >= buffer.size()) return NULL; //using pos to check whether buffer ends is better than using char* directly.
int value;
memcpy(&value, &buffer[pos], sizeof(int));
if (value < minValue || value > maxValue) return NULL;
TreeNode* node = new TreeNode(value);
pos += sizeof(int);
node->left = reconstruct(buffer, pos, minValue, value);
node->right = reconstruct(buffer, pos, value, maxValue);
return node;
}
};
// 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;