PAT-A1115

#include<stdio.h> #include<queue> using namespace std; struct pnode{ int data; pnode* left; pnode* right; int level; pnode():left(NULL),right(NULL){} }; int num_last=0, num_second=0, maxlevel=0; void insert(pnode* &root, int k){ if(root==NULL){ root=new pnode; root->data=k; return ; } if(k<=root->data)insert(root->left,k); else insert(root->right,k); } void BFS(pnode* &root){ queue<pnode* > q; root->level=1; q.push(root); while(!q.empty()){ pnode* front=q.front(); q.pop(); if(front->level>maxlevel)maxlevel=front->level; if(front->left!=NULL){ front->left->level=front->level+1; q.push(front->left); } if(front->right!=NULL){ front->right->level=front->level+1; q.push(front->right); } } } void BFScount(pnode* &root){ queue<pnode* > q; q.push(root); while(!q.empty()){ pnode* front=q.front(); q.pop(); if(front->level==maxlevel)num_last++; if(front->level==maxlevel-1)num_second++; if(front->left!=NULL){ q.push(front->left); } if(front->right!=NULL){ q.push(front->right); } } } int main(){ int i, n, t; pnode* root=NULL; scanf("%d",&n); for(i=0;i<n;i++){ scanf("%d",&t); insert(root,t); } BFS(root); BFScount(root); printf("%d + %d = %d",num_last,num_second, num_last+num_second); return 0; }