PAT(Advanced Level)A1115. Counting Nodes in a BST

题意

根据要求插入节点到BST里面，最后要输出最低的两层的结点树木

思路

• 先按照BST来建树，建树之后用dfs来统计每一层的结点数，同时要用一个变量来记住最大深度，那么我们就可以得到最低两层的结点数量了

代码

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string.h>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;
int cnt[1010] = {0};
int max_depth = -1;
struct node {
    int val;
    struct node* left;
    struct node* right;
    node(int x): val(x), left(NULL), right(NULL) {}
};
void insert(node*& root, int x) {
    if(root == NULL) {
        root = new node(x);
        return;
    }
    if(x > root->val)
        insert(root->right, x);
    else
        insert(root->left, x);
    return;
}
void dfs(node* root, int depth) {
    if(root) {
        cnt[depth]++;
        max_depth = max(max_depth, depth);
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);
    }
}
int main() {
    int N, t;
    cin >> N;
    node* root = NULL;
    while(N--) {
        cin >> t;
        insert(root, t);
    }
    dfs(root, 0);
    int sum = cnt[max_depth - 1] + cnt[max_depth];
    cout << cnt[max_depth] << " + " << cnt[max_depth - 1] << " = " << sum;
    return 0;
}