PAT a1115

目的：构建二叉搜索树，统计最下面两层的结点个数

输入：

N  <=1000 节点个数

序列

输出：

n1  最下面一行的结点个数

n2  倒数第二场的结点个数

算法：

构建树，一个点一个点的插入，同时 记录这个点的层数，把这个点的层数放进链表中或者数组对应层数的值加1.

同时每插入一个点，更新最大层数。

当所以点都插入完毕。根据最大层数，遍历vector统计最下层或者倒数第二层的结点个数。

#include<stdio.h>
#include<vector>

using namespace std;

struct node{
    int val;
    node* left;
    node* right;
};
vector<int> ans;
vector<int> sq;
int N,maxlayer = 0;
node* newnode(int x)
{
    node* now = new node;
    now->val = x;
    now->left = NULL;
    now->right = NULL;
    return now;
}
void insert(node* &root,int x,int layer)
{
    if(root==NULL)
    {
        root = newnode(x);
        ans.push_back(layer);
        if(layer>maxlayer)
        {
            maxlayer = layer;
        }
        return;
    }
    if(x<=root->val)
    {
        insert(root->left,x,layer+1);
    }else
    {
        insert(root->right,x,layer+1);
    }
}
int main()
{
    scanf("%d",&N);
    node* root = NULL;
    for(int i=0;i<N;i++)
    {
        int v;
        scanf("%d",&v);
        insert(root,v,1);
    }
    int n1 = 0,n2 = 0;
    for(int i=0;i<ans.size();i++)
    {
        if(ans[i]==maxlayer)
        {
            n1++;
        }else if(ans[i]==maxlayer-1)
        {
            n2++;
        }
    }
    printf("%d + %d = %d",n1,n2,n1+n2);
    return 0;
}