-
Notifications
You must be signed in to change notification settings - Fork 52
/
Serialize and Deserialize Binary Tree.cpp
111 lines (93 loc) · 2.78 KB
/
Serialize and Deserialize Binary Tree.cpp
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/*
* Solution 1
* Use to_string to convert integer to a string.
* Use space to separate each node.
* Write a '#' for nullptr node.
*/
class Codec {
void readNext(stringstream& ss, int& val, bool &isnumber) {
string str;
ss >> str;
if(str[0] == '#') {
isnumber = false;
} else {
val = stoi(str);
isnumber = true;
}
return;
}
TreeNode* help(stringstream& ss) {
bool isnumber;
int val;
TreeNode *root = nullptr;
readNext(ss, val, isnumber);
if (isnumber) {
root = new TreeNode(val);
root->left = help(ss);
root->right = help(ss);
}
return root;
}
// Encodes a tree to a single string.
string _serialize(TreeNode* root) {
if (root == nullptr) return "# ";
else return to_string(root->val) + " " + _serialize(root->left) + _serialize(root->right);
}
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string serialized_data = _serialize(root);
return serialized_data;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
stringstream ss(data);
return help(ss);
}
};
/*
* Solution 2
* Write 4 bytes for each integer.
* Write a 'Y' or 'N' for each node. No separator is need.
*/
class Codec {
void preorderDFS(TreeNode* root, string& serialized_data) {
if (root == nullptr) {
serialized_data.push_back('Y');
return;
}
serialized_data.push_back('N');
char buf[4];
memcpy(buf, &(root->val), sizeof(int));
for (int i = 0; i < 4; i++) serialized_data.push_back(buf[i]);
preorderDFS(root->left, serialized_data);
preorderDFS(root->right, serialized_data);
}
inline TreeNode* reconstruct(const string& buffer, int& pos) {
if (pos >= buffer.size()) return nullptr;
char indicator = buffer[pos];
pos++;
if (indicator == 'Y') {
return nullptr;
}
int value;
memcpy(&value, &buffer[pos], sizeof(int));
TreeNode* node = new TreeNode(value);
pos += sizeof(int);
node->left = reconstruct(buffer, pos);
node->right = reconstruct(buffer, pos);
return node;
}
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string serialized_data;
preorderDFS(root, serialized_data);
return serialized_data;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int pos = 0;
return reconstruct(data, pos);
}
};