关于c++:PAT甲级1115-Counting-Nodes-in-a-BST

题目粗心

给定一颗二叉搜寻树的插入序列，计算最初两层的节点个数

算法思路

首先咱们将这 n 个数字顺次插入到二叉搜寻树中，而后应用层序遍历获取每一层节点的数目和最大层数 maxLevel，L[maxLevel],L[maxLevel-1] 就是最初一层和倒数第二层的节点个数

提交后果

AC 代码

#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

struct Node{
    int val;
    Node* left;
    Node* right;
    int level;
};

/// 将 x 插入到 root 中
void insert(Node* &root,int x){if(root== nullptr){
        root = new Node;
        root->val = x;
        root->left = nullptr;
        root->right = nullptr;
        return;
    }
    if(root->val<x){insert(root->right,x);
    }else{insert(root->left,x);
    }
}

// 依据数组 arr 建树
Node* createTree(int arr[],int n){
    Node* root = nullptr;
    for(int i=0;i<n;++i){insert(root,arr[i]);
    }
    return root;
}

int L[1000];// 每一层的节点个数
int maxLevel = -1;

void layerOrder(Node* root){
    queue<Node*> que;
    root->level = 1;
    que.push(root);
    while(!que.empty()){Node* t = que.front();
        que.pop();
        maxLevel = max(maxLevel,t->level);
        ++L[t->level];
        if(t->left){
            t->left->level = t->level + 1;
            que.push(t->left);
        }
        if(t->right){
            t->right->level = t->level + 1;
            que.push(t->right);
        }
    }
}

int main() {
    int n;
    scanf("%d",&n);
    int initial[n];
    for(int i=0;i<n;++i){scanf("%d",&initial[i]);
    }
    Node* root = createTree(initial,n);
    layerOrder(root);
    printf("%d + %d = %d",L[maxLevel],L[maxLevel-1],L[maxLevel-1]+L[maxLevel]);
    return 0;
}