PAT 1115

#include<cstdio> #include<algorithm> #include<vector> #include<iostream> #include<queue> using namespace std; const int maxn = 1010; int in[maxn]; struct Node { Node* lchild; Node* rchild; int data; int depth; }; void insert(Node* &root,int a) { if (root == NULL) { root = new Node; root->lchild = root->rchild = NULL; root->data = a; return; } if (a <= root->data) insert(root->lchild, a); else insert(root->rchild, a); } int dep[maxn] = {0}; void bfs(Node* root) { if (root == NULL) return; queue<Node*> q; q.push(root); root->depth = 0; while (!q.empty()) { Node* top = q.front(); q.pop(); dep[top->depth]++; if (top->lchild!=NULL) { q.push(top->lchild); top->lchild->depth = top->depth+1; } if (top->rchild != NULL) { q.push(top->rchild); top->rchild->depth = top->depth+1; } } } int main() { int n; cin >> n; Node* root = NULL; for (int i=0;i<n;i++) { cin >> in[i]; insert(root,in[i]); } bfs(root); int i; for (i=0;i<n;i++) { if (dep[i] == 0) break; } i--; if (i >= 1) { cout << dep[i] << " + " << dep[i - 1] << " = " << dep[i] + dep[i - 1] << endl; } else cout << dep[i] << " + " << '0' << " = " << dep[i] << endl; system("pause"); return 0; }