1115 Counting Nodes in a BST (30 分)

水~。

题意

给定一棵二叉查找树(BST)的插入序列，求这棵二叉查找树的最下面两层的结点个数并求和。

注意点

与根结点相同的结点应当插到左子树中。

const int N=1010;
PII tree[N];
int a[N];
int dep[N],maxdep;
int cnt[N];
int n;

void insert(int &root,int idx)
{
    if(root == -1)
    {
        root=idx;
        tree[root]={-1,-1};
        return;
    }

    if(a[idx] <= a[root])
        insert(tree[root].fi,idx);
    else
        insert(tree[root].se,idx);
}

void bfs(int root)
{
    queue<int> q;
    q.push(root);
    dep[root]=1;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        maxdep=max(maxdep,dep[t]);
        cnt[dep[t]]++;

        if(~tree[t].fi)
        {
            dep[tree[t].fi]=dep[t]+1;
            q.push(tree[t].fi);
        }

        if(~tree[t].se)
        {
            dep[tree[t].se]=dep[t]+1;
            q.push(tree[t].se);
        }
    }
}

int main()
{
    cin>>n;

    int root=-1;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(root,i);
    }

    bfs(root);

    cout<<cnt[maxdep]<<" + "<<cnt[maxdep-1]<<" = "<<cnt[maxdep]+cnt[maxdep-1]<<endl;
    //system("pause");
    return 0;
}