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
结尾无空行

Sample Output:

2 + 4 = 6
结尾无空行

思路

二叉排序树的建立，求某层的节点个数。比较常规的出题了，但是二叉排序树在pat真题中出现过多次，每次都是三行描述，这次省略没看，居然就发现有细节的变化，直接影响结果。之前是相同的数放在右子树上，这次是放在左子树上。

建树的时候，就保存深度信息，无需二次遍历，很方便。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
int num[maxn];
int ans[maxn];
int maxdepth = 0;

struct node{
    int data;
    node* leftchild;
    node* rightchild;
    int depth;
    node(int d, int dep): data(d), depth(dep), leftchild(NULL), rightchild(NULL) {
    }
};

node* create(node* root, int data, int depth) {
    if (root == NULL) {
        root = new node(data, depth);
        if (depth > maxdepth) maxdepth = depth;
        ans[depth]++;
        return root;
    }
    if (data <= root->data) {
        root->leftchild = create(root->leftchild, data, depth + 1);
    } else if (data > root->data) {
        root->rightchild = create(root->rightchild, data, depth + 1);
    }
    return root;
}

int main() {
    int len;
    cin>>len;
    node* root = NULL;
    for (int i = 0; i < len; i++) {
        ans[i] = 0;
    }
    for (int i = 0; i < len; i++) {
        cin>>num[i];
        root = create(root, num[i], 0);
    } 
    printf("%d + %d = %d", ans[maxdepth], ans[maxdepth - 1], ans[maxdepth] + ans[maxdepth - 1]);
    
}