本文共 1290 字，大约阅读时间需要 4 分钟。

题意:

按照输入序列建一颗二叉搜索树，输出最下面一层和倒数第二层点数之差

题解:

BST基础题，范围比较大，不能用数组模拟，用指针来写

#include
   
    using namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef  long long LL;const int INF = 1 << 30;const int MAXN = 100010;struct node{
       node *l, *r;    int v, depth;    node(node *ll, node *rr, int vv){
   l = ll, r = ll, v = vv;}};int maxDepth = 0, n1 = 0, n2 = 0;node* Insert(node *root, int v){
       if(root == NULL)        root = new node(NULL, NULL, v);    else if(v <= root->v)        root->l = Insert(root->l, v);    else        root->r = Insert(root->r, v);    return root;}void setDepth(node *root, int d){
       root->depth = d;    maxDepth = max(maxDepth, d);    if(root->l)        setDepth(root->l, d+1);    if(root->r)        setDepth(root->r, d+1);}void Dfs(node *root, int d){
       if(root->depth == maxDepth)        ++n1;    else if(root->depth == maxDepth-1)        ++n2;    if(root->l)        Dfs(root->l, d+1);    if(root->r)        Dfs(root->r, d+1);}int main() {
       ios::sync_with_stdio(false);    int v, n;    cin >> n >> v;    node *root = new node(NULL, NULL, v);    for(int i = 2; i <= n; ++i)        cin >> v, Insert(root, v); //1为根节点    setDepth(root, 1);    Dfs(root, 1);    cout << n1 << " + " << n2 << " = " << n1+n2 << endl;    return 0;}//6 5 4 6 2 1 7
   

转载地址：https://suprit.blog.csdn.net/article/details/104166968 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！