1115 Counting Nodes in a BST (30point(s))

我会带着你远行 2024-05-08 06:07 59阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

1、构建一棵二叉搜索树，注意左子树是小于等于；  
2、层次遍历每一层的节点个数；  
3、输出最后两层结点个数；

感觉没什么问题啊，为什么只能部分通过，明天再说吧！！！

##### 代码 #####

#include <iostream>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    #include <stack>
    #include <set>
    #include <queue>
    #include <malloc.h>
    #include <math.h>
    
    using namespace std;
    const int maxn = 1010;
    int num[maxn], depth = 0;//num存储每层的结点个数，depth存储树的高度
    
    typedef struct node{
        
         int value;
         struct node *left, *right;
    }BiNode;
    
    typedef pair<BiNode*, int> elem;//first代表指向此结点的指针，second代表此结点所在高度
    
    
    //insert elem to BST
    void insert_to_BST(BiNode* biNode, BiNode* &root){
        
         if(root == NULL) root = biNode;
         else{
        
              if(biNode->value <= root->value) insert_to_BST(biNode, root->left);
              else insert_to_BST(biNode, root->right);
         }
    }
    
    //void BFS(BiNode *root){
        
    //     if(!root) return; //如果为空，直接结束
    //     queue<elem> Q;
    //     elem e = make_pair(root, 1);
    //     Q.push(e);
    //     while(!Q.empty()){
        
    //          e = Q.front();//取队首元素
    //          Q.pop();
    //          //printf("%d %d\n", e.first->value, e.second);
    //          depth = max(depth, e.second);//更新树的深度
    //          num[e.second]++;//更新每层的结点个数
    //          //把非空的左子树和右子树放入队列
    //          if(e.first->left) Q.push(make_pair(e.first->left, e.second + 1));
    //          if(e.first->right) Q.push(make_pair(e.first->right, e.second + 1));
    //     }
    //}
    
    void DFS(BiNode *root, int level){
        
         if(root == NULL) return;
         num[level]++;
         depth = max(depth, level);
         DFS(root->left, level + 1);
         DFS(root->right, level + 1);
    }
    
    int main()
    {
        
         memset(num, 0, sizeof(num));//initialize number of layer
         BiNode *root = NULL;
         int n, temp;
         scanf("%d", &n);
         for(int i = 0; i < n; i ++){
        
              BiNode *biNode = (BiNode*)malloc(sizeof(BiNode));
              scanf("%d", &temp);
              biNode->value = temp;
              biNode->left = biNode->right = NULL;
              insert_to_BST(biNode, root);
         }
         //BFS(root);
         DFS(root, 1);
         printf("%d + %d = %d\n", num[depth - 1], num[depth], num[depth - 1] + num[depth]);
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805355987451904