1115 Counting Nodes in a BST (30分)

题目链接：1115 Counting Nodes in a BST (30分)

题意

给出二叉排序树的输入序列，其中小于等于根节点的放左边，大于根节点的放右边。构建完二叉排序树够计算最下面一层的元素个数n1 ,和倒数第二层的元素个数n2，计算n1 + n2

分析

根据序列构造二叉树，然后层序遍历，计算n1,n2.

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue> 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */using namespace std;
typedef struct Tree{
    int data, level;struct Tree *ltree, *rtree;
}Tree, *BiTree;
void add(BiTree &root, int x);
void bfs(BiTree root, int &n1, int &n2);
int questHigh(BiTree root);
int main(int argc, char** argv) {
    int n, x, n1 = 0, n2 = 0;BiTree root = NULL;scanf("%d", &n);for (int i = 0; i < n; i++) {
    scanf("%d", &x);add(root, x);}bfs(root, n1, n2);	printf("%d + %d = %d", n1, n2, n1 + n2);return 0;}
void add(BiTree &root, int x) {
    if (root == NULL) {
    root = (BiTree) malloc(sizeof(Tree));root->data = x;root->ltree = root->rtree = NULL;} else if (root->data >= x) {
    add(root->ltree, x);} else {
    add(root->rtree, x);}
}
void bfs(BiTree root, int &n1, int &n2) {
    root->level = 1;int h = questHigh(root);queue<BiTree> que;que.push(root);while(!que.empty()) {
    BiTree t = que.front();que.pop();if (t->ltree) {
    t->ltree->level = t->level + 1;que.push(t->ltree);}if (t->rtree) {
    t->rtree->level = t->level + 1;que.push(t->rtree);}if (t->level == h)n1++;if (t->level == h - 1)n2++;}
}
int questHigh(BiTree root) {
    if (root == NULL) return 0;int l = questHigh(root->ltree);int r = questHigh(root->rtree);return l > r ? l + 1 : r + 1;
}