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.
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.
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.
Sample Input:
10
25 30 42 16 20 20 35 -5 28 22
Sample Output:
3 + 4 = 7题目大意：给出n个节点，构建一棵二叉搜索树，输出它最后两层结点个数a和b，以及它们的和c：“a + b = c”
分析：先建树，每个节点额外增加深度标签。建树时记录最深的深度，最后bfs找到最深和次深的节点个数即可。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#define INF 0xffffffff
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<endl
#define db5(x,y,z,r,w) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#r<<"="<<(r)<<", "<<#w<<"="<<(w)<<endl
using namespace std;typedef struct node
{int val,depth;struct node *left,*right;
}node;void Freenode(node *p)
{if(p==NULL)return;Freenode(p->left);Freenode(p->right);free(p);return;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint n,maxn=0;scanf("%d",&n);node *root=(node*)malloc(sizeof(node));for(int i=0;i<n;++i){int a;scanf("%d",&a);if(!i)root->val=a,root->left=root->right=NULL,root->depth=0;else{node *p=(node*)malloc(sizeof(node));p->val=a;p->left=p->right=NULL,p->depth=0;node *q=root;while(q!=NULL){
// db3(q->val,q->depth,a);if(q->val<a){if(q->right==NULL){q->right=p;p->depth=q->depth+1;maxn=max(maxn,p->depth);break;}else q=q->right;}else{if(q->left==NULL){q->left=p;p->depth=q->depth+1;maxn=max(maxn,p->depth);break;}else q=q->left;}}}}// db3(root->val,root->left->val,root->right->val);int n1=0,n2=0;queue<node*>que;que.push(root);while(!que.empty()){node *temp=que.front();que.pop();// db2(temp->val,temp->depth);if(temp->depth==maxn-1)n1++;else if(temp->depth==maxn)n2++;if(temp->left!=NULL)que.push(temp->left);if(temp->right!=NULL)que.push(temp->right);}printf("%d + %d = %d",n2,n1,n1+n2);Freenode(root);#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}
