-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathalgorithmsBasic.cpp
More file actions
68 lines (63 loc) · 1.57 KB
/
algorithmsBasic.cpp
File metadata and controls
68 lines (63 loc) · 1.57 KB
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
#include "algorithmsBasic.hpp"
TreeNode* make_Tree(string data) {
if(data.size() == 0)
return NULL;
int start = 0, elemNum = 1;
return deserialize(data);
}
TreeNode* getTreeNode(string str) {
if(str.size() == 0)
return NULL;
if('#' == str[0])
return NULL;
return new TreeNode(stoi(str));
}
TreeNode *deserialize(const string &data) {
if (0 == data.size())
return NULL;
int idx = data.find(",", 0);
TreeNode *root;
queue<TreeNode*> q;
if (NULL != (root = getTreeNode(data.substr(0, idx))))
q.push(root);
if (q.empty())
return root;
int elemNum = 2;
++idx;
deserialize(data, idx, elemNum, q);
return root;
}
void deserialize(const string &data, int &start, int elemNum, queue<TreeNode*> &q) {
if(!(start < (int)data.size())) {
while(!q.empty())
q.pop();
return ;
}
int idx;
for(int i = 1; i < elemNum;) {
TreeNode *root = q.front();
q.pop();
if(NULL == root) {
i += 2;
continue;
}
idx = data.find(",", start);
if(NULL != (root->left = getTreeNode(data.substr(start, idx - start))))
q.push(root->left);
start = idx + 1;
++i;
idx = data.find(",", start);
if(NULL != (root->right = getTreeNode(data.substr(start, idx - start))))
q.push(root->right);
start = idx + 1;
++i;
}
deserialize(data, start, elemNum << 1, q);
}
void preorder(TreeNode* root) {
if (NULL == root)
return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}