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 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.

blablabla

Sample Input:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int n;
int l[N],r[N],v[N],idx;
int cnt[N],max_depth;

void insert(int &u,int w)  //递归插入结点，
{
    if(!u)
    {
        u=++idx;
        v[u]=w;
    }

    else if(w<=v[u]) insert(l[u],w);
    else insert(r[u],w);
}

void dfs(int u,int depth)  //求每一层结点数
{
    if(!u) return;
    cnt[depth]++;
    max_depth=max(max_depth,depth);
    dfs(l[u],depth+1);
    dfs(r[u],depth+1);

}
int main()
{
    cin>>n;

    int root=0;
    for(int i=0;i<n;i++)
    {
        int w;
        cin>>w;
        insert(root,w);
    }

    dfs(root,0);

    int n1=cnt[max_depth],n2=cnt[max_depth-1];
    printf("%d + %d = %d\n",n1,n2,n1+n2);

    return 0;
}