1115 二叉搜索树最后两层结点数量

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 它的左、右子树也分别为二叉搜索树

将一系列数字按顺序插入到一个空的二叉搜索树中，然后，请你计算结果树的最低两层的结点个数。

输入格式

第一行包含整数 N，表示插入数字序列包含的数字个数。

第二行包含 N 个整数，表示插入数字序列。

输出格式

以如下格式，在一行中，输出结果树的最后两层的结点数：

n1 + n2 = n

n1 是最底层结点数量，n2 是倒数第二层结点数量，n 是它们的和。

数据范围

1≤N≤1000,
−1000≤ 插入数字 ≤1000。

输入样例：

9
25 30 42 16 20 20 35 -5 28

输出样例：

2 + 4 = 6

代码实现：

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1005;
int l[N],r[N],w[N],vis[N],root,idx,max1;
int level[N];
void build(int &u,int x){
    if(!u)u=++idx,w[u]=x;
    else if(x<=w[u])build(l[u],x);
    else build(r[u],x);
}
void bfs(int x){
    queue<pair<int,int> >q;
    q.push({x,1});
    while(q.size()){
        int s=q.front().first;
        int dis=q.front().second;
        q.pop();
        if(vis[s])continue;
        vis[s]=1;
        max1=max(max1,dis);
        level[dis]++;
        if(l[s])q.push({l[s],dis+1});
        if(r[s])q.push({r[s],dis+1});
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        build(root,x);
    }
    bfs(root);
    cout<<level[max1]<<" + "<<level[max1-1]<<" = "<<level[max1-1]+level[max1]<<endl;
    return 0;
}