按给定序列构造一个二叉搜索树, 分别计算最低两层的节点数量
思路: 如题, 考基本功
注意: 一种新奇的写法, 获取倒数第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; }
|