AcWing 1605. 二叉搜索树最后两层结点数量
原题链接
中等
作者:
麦克斯韦妖_7
,
2021-08-26 17:08:13
,
所有人可见
,
阅读 215
#include <iostream>
using namespace std;
int level = 1;
int hashtable[1010] = {0};
struct node{
int data, level;
node *left, *right;
};
void insert(node* &root, int data){
if(root == NULL){
root = new node;
root->data = data;
root->left = root->right = NULL;
return;
}
if(data <= root->data) insert(root->left, data); /*这道题根据样例来说,等于时放在左子树*/
else insert(root->right, data);
}
void DFS(node *root, int level){
if(root == NULL){
return;
}
DFS(root->left, level + 1);
DFS(root->right, level + 1);
root->level = level;
hashtable[level] ++;
}
int main(){
int n;
cin >> n;
node* root = NULL;
for(int i = 0; i < n; i ++){
int temp;
cin >> temp;
insert(root, temp);
}
DFS(root, 1);
for(int i = 1; i <= n; i ++){
if(hashtable[i] == 0){
cout << hashtable[i - 1] << " + " << hashtable[i - 2] << " = ";
cout << hashtable[i - 1] + hashtable[i - 2] << endl;
break;
}
}
return 0;
}