个人练习-PAT甲级-1115 Counting Nodes in a BST

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805355987451904

题目大意：建BST，求树最后两层的元素数。

思路：开始想用数组建树。然而skewing tree的极端情况树可能有一千层，空间太大了，不行。于是老老实实用Node类建树，需要的时候才开新空间。在每次insert的时候就计算好层次，并把元素插入对应的arr[lvl]里。

Node* insert(Node* node, int num, int lvl) {
    if (node == nullptr) {
    node = new Node();node->val = num;arr[lvl].push_back(num);return node;}if (num <= node->val)node->left = insert(node->left, num, lvl+1);elsenode->right = insert(node->right, num, lvl+1);return node;
}

最后直接数最后两个有元素的arr[]的size即可。如果只有最后一层有元素，那么倒二层个数就是0。

    int ml;for (ml = 1000; ml >= 0; ml--) {
    if (arr[ml].size() != 0)break;}n1 = arr[ml].size();if (ml == 0)n2 = 0;elsen2 = arr[ml-1].size();

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>using namespace std;class Node {
    
public:int val;Node* left;Node* right;Node() {
    left = nullptr;right = nullptr;}
};vector<int> arr[1001];Node* insert(Node* node, int num, int lvl) {
    if (node == nullptr) {
    node = new Node();node->val = num;arr[lvl].push_back(num);return node;}if (num <= node->val)node->left = insert(node->left, num, lvl+1);elsenode->right = insert(node->right, num, lvl+1);return node;
}int main() {
    int N, n1, n2;scanf("%d", &N);Node* head = nullptr;for (int i = 0; i < N; i++) {
    int tmp;scanf("%d", &tmp);head = insert(head, tmp, 0);}int ml;for (ml = 1000; ml >= 0; ml--) {
    if (arr[ml].size() != 0)break;}n1 = arr[ml].size();if (ml == 0)n2 = 0;elsen2 = arr[ml-1].size();printf("%d + %d = %d", n1, n2, n1+n2);return 0;
}