本文主要是介绍力扣二叉树的构造
即，从[x, x, x, x, x]为层序遍历的结果来构造一颗二叉树
数据结构定义
树节点数据结构包括 — 值、左指针、右指针。
1
2
3
4
5
6
7
8
9
|
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr){}
TreeNode(int val) : val(val), left(nullptr), right(nullptr){}
TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right){};
};
|
力扣输入形式构造数组
根据[x, x, x, x, x]的形式创建数组
1
2
3
4
5
6
7
8
9
10
11
12
| string str;
getline(cin, str);
vector<int> vec;
int val = 0;
for(auto &ch:str) {
if(ch >= '0' && ch <= '9') {
val = val * 10 + ch - '0';
} else if(ch == ',' || ch == ']') {
vec.push_back(val);
val = 0;
}
}
|
用层序遍历结果建树
根据树用数组表示的特点（根节点角标与左右子树角标的关系）来递归构造二叉树
1
2
3
4
5
6
7
8
9
10
|
TreeNode *CreateTree(vector<int> &nums, int index) {
if (index >= nums.size() || nums[index] == 0) {
return nullptr;
}
TreeNode *node = new TreeNode(nums[index]);
node->left = CreateTree(nums, 2 * index + 1);
node->right = CreateTree(nums, 2 * index + 2);
return node;
}
|
层序遍历
层序遍历，验证与输入是否一致
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
vector<int> printTree(TreeNode * root) {
vector<int> temp;
queue<TreeNode *> que;
que.push(root);
while(!que.empty()) {
TreeNode *node = que.front();
que.pop();
temp.push_back(node->val);
if(node->left) {
que.push(node->left);
}
if(node->right) {
que.push(node->right);
}
}
return temp;
}
|
释放内存
1
2
3
4
5
6
7
8
9
|
void DeleteTree(TreeNode * root) {
if(root == nullptr) {
return;
}
DeleteTree(root->left);
DeleteTree(root->right);
delete root;
}
|
完整代码
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
| #include<bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr){}
TreeNode(int val) : val(val), left(nullptr), right(nullptr){}
TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right){};
};
TreeNode *CreateTree(vector<int> &nums, int index) {
if (index >= nums.size() || nums[index] == 0) {
return nullptr;
}
TreeNode *node = new TreeNode(nums[index]);
node->left = CreateTree(nums, 2 * index + 1);
node->right = CreateTree(nums, 2 * index + 2);
return node;
}
void DeleteTree(TreeNode * root) {
if(root == nullptr) {
return;
}
DeleteTree(root->left);
DeleteTree(root->right);
delete root;
}
vector<int> printTree(TreeNode * root) {
vector<int> temp;
queue<TreeNode *> que;
que.push(root);
while(!que.empty()) {
TreeNode *node = que.front();
que.pop();
temp.push_back(node->val);
if(node->left) {
que.push(node->left);
}
if(node->right) {
que.push(node->right);
}
}
return temp;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
string str;
getline(cin, str);
vector<int> vec;
int val = 0;
for(auto &ch:str) {
if(ch >= '0' && ch <= '9') {
val = val * 10 + ch - '0';
} else if(ch == ',' || ch == ']') {
vec.push_back(val);
val = 0;
}
}
TreeNode *root = CreateTree(vec, 0);
vector<int> res;
res = printTree(root);
cout << "[";
for (int i = 0; i < res.size(); ++i) {
cout << res[i];
if(i != res.size() - 1) {
cout << ",";
}
}
cout << "]";
DeleteTree(root);
return 0;
}
|