PAT (Advanced Level) Practice 1115 Counting Nodes in a BST (30 分) 凌宸1642

题目描述：

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

译：二叉搜索树 (BST) 递归地定义为具有以下属性的二叉树：

• 节点的左子树仅包含键小于或等于节点键的节点。

• 节点的右子树仅包含键大于节点键的节点。

• 左右子树也必须是二叉搜索树。

将一系列数字插入到最初为空的二叉搜索树中。 然后你应该计算结果树的最低 2 个级别中的节点总数。

Input Specification (输入说明):

Each input file contains one test case. For each case, the first line gives a positive integer N (≤1000) which is the size of the input sequence. Then given in the next line are the N integers in [−1000,1000] which are supposed to be inserted into an initially empty binary search tree.

译：每个输入文件包含一个测试用例。 对于每种情况，第一行给出一个正整数 N (≤1000)，它是输入序列的大小。 然后在下一行给出 [−1000,1000] 中的 N 个整数，它们应该被插入到最初为空的二叉搜索树中。

output Specification (输出说明):

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

译：对于每种情况，在一行中打印结果树的最低 2 级中的节点数，格式如下：

n1 + n2 = n

其中 n1 是最低层的节点数，n2 是上层的节点数，n 是总和。

Sample Input (样例输入):

9
25 30 42 16 20 20 35 -5 28

Sample Output (样例输出):

2 + 4 = 6

The Idea：

• 节点数不多，利用链式二叉树结构，根据输入的数据，简历二叉搜索树 BST。
• 对二叉搜索树进行层序遍历，并且记录层数以及每层节点的个数。
• 输出最后两层的算术和的算式。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1010 ;
int n , t , cnt = 0 ;
vector<int> ans ;
struct node{
	int val ;
	node* l ;
	node* r ;
};
void insert(node* &root , int data){
	if(!root){
		root = new node() ;
		root->val = data ;
		root->l = root->r = NULL ;
		return ;   // 一定要记得返回，不然会爆栈 
	}
	if(data <= root->val) insert(root->l , data) ;	
	else insert(root->r , data) ;	
}
void bfs(node* root){
	queue<node*> q ;
	q.push(root) ;
	while(!q.empty()){
		cnt ++ ;  // 记录总共有几层 
		int size = q.size() ;
		ans.push_back(size );
		for(int i = 0 ; i < size ; i ++){
			node* top = q.front() ;
			q.pop() ;
			if(top->l != NULL) q.push(top->l) ;  	// 左孩子不空，则入队 
			if(top->r != NULL) q.push(top->r) ;		// 右孩子不空，则入队 
		}
		
	}
}
int main(){
	cin >> n ;	
	node* root = NULL ;
	for(int i = 0 ; i < n ; i ++){
		cin >> t ;
		insert(root , t) ;
	}
	bfs(root) ;
	printf("%d + %d = %d\n" , ans[cnt - 1] , ans[cnt - 2] , ans[cnt - 1] + ans[cnt - 2]) ;
	return 0 ;
}