二叉搜索树的2层结点统计 (25 分)

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

将一系列数字按给定顺序插入一棵初始为空的二叉搜索树，你的任务是统计结果树中最下面 2 层的结点数。

输入格式：输入在第一行给出一个正整数

输出格式：在一行中输出最下面 2 层的结点总数。

输入样例：9 25 30 42 16 20 20 35 -5 28 输出样例：6

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int l[1005],r[1005],a[1005];
 4 int num[1005],max_d,n,x;
 5 void dfs(int root,int pos,int depth){
 6     if(a[pos] <= a[root]){
 7         if(l[root]==0x3f3f3f3f){
 8             l[root]=pos;
 9             num[depth+1]++;
10             max_d=max(max_d,depth+1);
11         }else{
12             dfs(l[root],pos,depth+1);
13 
14         }
15     }else{
16         if(r[root]==0x3f3f3f3f){
17             r[root]=pos;
18             num[depth+1]++;
19             max_d=max(max_d,depth+1);
20         }else{
21             dfs(r[root],pos,depth+1);
22         }
23     }
24 }
25 int main(){
26     memset(l,0x3f3f3f3f,sizeof l);
27     memset(r,0x3f3f3f3f,sizeof r);
28 
29     cin>>n;
30     if(n==1){
31         cout<<"1"<<endl;
32         return 0;
33     }
34     for(int i=0;i<n;i++){
35         cin>>x;
36         if(!i) a[i]=x;
37         else{
38             a[i]=x;
39             dfs(0,i,0);
40         }
41     }
42     cout<<num[max_d-1]+num[max_d];
43     return 0;
44 }

View Code