L2-3 二叉搜索树的2层结点统计
分数 25
作者 陈越
单位 浙江大学
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

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

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

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

输入样例：9
25 30 42 16 20 20 35 -5 28
输出样例：6

本来想用静态数组，结果感觉最大要2^1000，空间过不了，所以用指针

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
using namespace std;
int n;
struct tree
{
	tree* left;
	tree* right;
	int val;
	int height;
	tree() { left = NULL; right = NULL; val = 0; }
};
tree* lst;
int ans = 0;
void dfs(tree* t,int man)
{
	if (t->height > man - 2 and t->height <= man)ans++;
	if (t->right != NULL)dfs(t->right, man);
	if (t->left != NULL)dfs(t->left, man);
}
int main()
{
	lst = new tree;
	int n;
	
	cin >> n;
	int xx;
	cin >> xx;
	lst->val = xx;
	lst->height = 1;
	tree* start = lst;
	int heightmax = 1;
	for (int i = 1; i < n; i++)
	{
		start = lst;
		tree *next = new tree;
		cin >> xx;
		next->val = xx;
		while ( start->height <= heightmax)
		{
			if (next->val > start->val)
			{
				if (start->right != NULL)start = start->right;
				else break;
			}
			else
			{
				if (start->left != NULL)start = start->left;
				else break;
			}
		}
		if (next->val > start->val)
		{
			start->right = next;
		}
		else
		{
			start->left=next;
		}
		next->height = start->height + 1;
		heightmax = max(heightmax, next->height);
	}
	start = lst;
	dfs(start, heightmax);
	cout << ans << endl;
	return 0;
}