1115 Counting Nodes in a BST (30 分)

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

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

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

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.

Sample Input:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6


就是一个建树的问题，不值30分

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 struct Node{
 4     int val;
 5     Node *left, *right;
 6 };
 7 int n, x, vis[2000];
 8 int maxl = 0;
 9 Node *build(Node *root, int val){
10     if(root == NULL){
11         root = new Node();
12         root->val = val;
13         root->left = root->right = NULL;
14     }else{
15         if(val <= root->val){
16             root->left = build(root->left, val);
17         }else{
18             root->right = build(root->right, val);
19         }
20     }
21     return root;
22 }
23 void output(Node *root, int x){
24     if(root != NULL){
25         vis[x]++;
26         maxl = max(maxl,x);
27         output(root->left, x+1);
28         output(root->right, x+1);
29     }
30 }
31 int main(){
32     cin >> n;
33     Node *tree = NULL;
34     for(int i = 0; i < n; i++){
35         cin >> x;
36         tree = build(tree,x);
37     }
38     output(tree, 1);
39     cout << vis[maxl] <<" + "<<vis[maxl-1]<<" = "<<vis[maxl]+vis[maxl-1]<<endl;
40     return 0;
41 }