按给定序列构造一个二叉搜索树, 分别计算最低两层的节点数量
思路: 如题, 考基本功
注意: 一种新奇的写法, 获取倒数第n个元素 (想到了Python是不是XD)
1
2
3
|
cout << x.end()[-n] << endl;
|
代码(有内存泄漏):
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
| #include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
using namespace std;
struct node {
int val;
node *left, *right, *parent;
} root;
void insert(int x)
{
if (!root.parent) {
root.parent = &root;
root.val = x;
return;
}
node *p = &root;
while (true) {
if (x <= p->val) {
if (p->left) {
p = p->left;
} else {
break;
}
} else {
if (p->right) {
p = p->right;
} else {
break;
}
}
}
if (x > p->val) {
p->right = new node();
p->right->val = x;
p->right->parent = p;
} else {
p->left = new node();
p->left->val = x;
p->left->parent = p;
}
}
void trav()
{
queue<node *> Q;
if (root.parent) {
Q.push(&root);
}
Q.push(nullptr);
int lcount = 0;
vector<int> counts;
while (Q.size() > 1) {
node *x = Q.front();
Q.pop();
if (x == nullptr) {
counts.push_back(lcount);
lcount = 0;
Q.push(nullptr);
continue;
}
lcount++;
if (x->left)
Q.push(x->left);
if (x->right)
Q.push(x->right);
}
counts.push_back(lcount);
int back = counts.size() ? counts.back() : 0;
int back2 = counts.size() > 2 ? counts.end()[-2] : 0;
cout << back << " + " << back2 << " = " << back + back2 << endl;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
insert(x);
}
trav();
return 0;
}
|