2020 天梯模拟赛 L2-3 二叉搜索树的2层结点统计

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

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

输入格式：输入在第一行给出一个正整数 N (≤1000)，为插入数字的个数。第二行给出 N 个 [−1000,1000] 区间内的整数。数字间以空格分隔。

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

输入样例：

9
25 30 42 16 20 20 35 -5 28

输出样例：

6

这道题的思路就是先用递归的思想，将一个一个结点存入树当中，然后再对这棵树进行遍历，到最下面2层的时候，就开始对结点计数。

#include<bits/stdc++.h>
using namespace std;
int maxn=0,num=0;//maxn用来记录树的最大深度，num用来记录最下面两层的结点数 
typedef struct Tnode//定义树的结构体 
{
	int data;
	Tnode *lchild;
	Tnode *rchild;
}*Bitree;
void create_tree(Bitree &T,int x,int h)
{
 	if(T==NULL)
 	{  
		T=(Bitree)malloc(sizeof(Tnode));
		T->data=x;
		T->lchild=NULL;
		T->rchild=NULL;
		if(maxn<h)//及时更新maxn的值 
			maxn=h;
	}
	else if(x<=T->data)//根据题意，小于等于根结点的值就放在左子树上 
		create_tree(T->lchild,x,h+1);
	else create_tree(T->rchild,x,h+1);//大于根结点的值就放在右子树上 
}
int preorder(Bitree T,int h)//先序遍历 
{
	if(T==NULL) return 0;
 	if(h>=maxn-1) num++;//如果已经在最下面两层，就开始对结点计数 
 	preorder(T->lchild,h+1);
 	preorder(T->rchild,h+1);
 	return 1;
}
int main()
{
	int n,x;
	Bitree T=NULL;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		create_tree(T,x,1);
	}
	preorder(T,1);
	cout<<num;
	return 0;
}