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:

9
25 30 42 16 20 20 35 -5 28

2 + 4 = 6

## 解答

#include<iostream>
#include<queue>

using namespace std;

struct Node{
int key;
Node *lchild, *rchild;
};

void Insert(Node *&root, int key)
{
if (root == NULL) {
root = new Node();
root->key = key;
return;
}
if (key <= root->key) Insert(root->lchild, key);
else Insert(root->rchild, key);
}

int main()
{
int key, n;
cin >> n;
Node *root = NULL;
for(int i=0;i<n;i++){
cin >> key;
Insert(root, key);
}
queue<Node*> q;
Node* p = NULL;
int currentC = 1, nextC = 0, i = 0, preC = 0;
int last2 = 0, last1 = 0;
q.push(root);
while (!q.empty()) {
p = q.front();
q.pop();
i++;
if (p->lchild) {
q.push(p->lchild);
nextC++;
}
if (p->rchild) {
q.push(p->rchild);
nextC++;
}
if (i == currentC) {
if (nextC != 0) {
preC = currentC;
currentC = nextC;
}
nextC = 0;
i = 0;
}
}
printf("%d + %d = %d", currentC, preC, preC + currentC);
return 0;
}