题意：给出一个序列，构建二叉搜索树(BST)，输出二叉搜索树最后两层的节点个数n1和n2，以及他们的和sum：
n1 + n2 = sum
递归建树，然后再dfs求出最大层数，接着再dfs计算出最后两层的节点个数，也可以直接一遍dfs，顺便存储各个层的节点数。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#define LEFT 1
#define RIGHT 2
using namespace std;
/*
建立BST，两次dfs
一开始直接用index表示二叉树
即节点i的左孩子为2*i，右孩子为2*i+1
但是这样就会导致超出存储大小。。。
*/
const int maxn=+; //一开始设置成了1000导致段错误
int a[maxn];
int maxlayer=;
int n1=,n2=;
int cnt;
struct Node{
int left=-,right=-;
int id=-;
int value;
}node[maxn];
/*
root is the current node
val is the value of root
fa is the father node of root
LR tells that root is left or right child of fa
*/
void insertBST(int root,int val,int fa,int LR){
if(root==-){
cnt++;
node[cnt].value=val;
if(LR==LEFT){
node[fa].left=cnt;
}
else{
node[fa].right=cnt;
}
return;
}
if(val<=node[root].value){
insertBST(node[root].left,val,root,LEFT);
}
else{
insertBST(node[root].right,val,root,RIGHT);
}
}
void dfs(int root,int layer){
if(root==-){
maxlayer=max(maxlayer,layer-);
return;
}
dfs(node[root].left,layer+);
dfs(node[root].right,layer+);
} void dfsAns(int root,int layer){
if(root==-){
return;
}
if(layer==maxlayer){
n1++;
}
if(layer==maxlayer-){
n2++;
}
dfsAns(node[root].left,layer+);
dfsAns(node[root].right,layer+);
}
int main()
{
int n;
scanf("%d",&n);
int a;
memset(node,-,sizeof(node));
scanf("%d",&a);
node[].value=a;
cnt=;
for(int i=;i<n;i++){
scanf("%d",&a);
insertBST(,a,-,-);
}
dfs(,);
dfsAns(,);
printf("%d + %d = %d",n1,n2,n1+n2);
return ;
}