【dfs】PAT甲级 1115 Counting Nodes in a BST

1115 Counting Nodes in a BST

解题思路

考察 dfs，在建树的过程中统计每层的节点数。

注意事项

认真看题目的定义，若当前 val <= root->val 则插入左子树。

参考代码

#include<stdio.h>
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<stack>
//#define LOCAL  //提交时一定注释
#define VI vector<int>
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long LL;
typedef double db;
const int inf = 0x3f3f3f3f;
const LL INF = 1e18;
const int N = 1e4 + 10;

inline int readint() {int x; scanf("%d", &x); return x;}

struct node{
    int val;
    node *l, *r;
    node() {l = r = NULL;}
};
int num[N];
int maxd = -1;
void insert(node *&root, int val, int depth) {
    if (root == NULL) {
        num[depth]++;
        maxd = max(depth, maxd);
        root = new node;
        root->val = val;
        return;
    }
    if (val <= root->val) insert(root->l, val, depth + 1);
    else insert(root->r, val, depth + 1);
}


int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
#endif
    int n = readint();
    node *root = NULL;
    for(int i = 0; i < n; ++i) {
        insert(root, readint(), 1);
    }
    printf("%d + %d = %d\n", num[maxd], num[maxd - 1], num[maxd] + num[maxd - 1]);

    return 0;
}