1115. Counting Nodes in a BST (30)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following PRoperties:

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

925 30 42 16 20 20 35 -5 28Sample Output:
2 + 4 = 6题意：计算二叉搜索树最后两层的结点数
#include <cstdio>#include <cstring>#include <iostream>#include <stdlib.h>using namespace std;struct node{    int v;    node *left;    node *right;    node(int v):v(v),left(NULL),right(NULL){}};int n, t, a[1010] = {0};void build(node* &root, int v, int step){    if(root == NULL)    {        root = new node(v);        a[step]++;        return;    }    if(v <= root->v) build(root->left, v, step+1);    else build(root->right, v, step+1);}int main(){    node* root = NULL;    scanf("%d", &n);    for(int i = 0; i < n; i++)    {        scanf("%d", &t);        build(root, t, 1);    }    int last = 0;    for(int i = 1; a[i]!=0; i++)        last = i;    printf("%d + %d = %d/n", a[last], a[last-1], a[last] + a[last-1]);    return 0;}