这道题我最开始题目理解错了,最开始我理解成了统计叶子节点和叶子节点的上一层的结点数量。一提交得了2分,这时我知道我题目肯定读错了。
后来又做了一次,然后提交得了8分,我实在想不出有什么地方没写对,但是就是通不过。
后来认真读了一遍题目,才发现这个二叉搜索树种有重复数值的结点,而且要按照题目,把小于等于根结点的数据放在左子树,我想当然的放在了右子树,所以导致了错误,后来把这个错误改正过来了,一提交,果然通过了。
这个故事告诉我们认真读题是多么的重要。
后来翻看别人博客的时候,看到有个很简洁的写法,所以就办了过来。在插入的时候,同时记录结点的层数。
简洁版
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
int data;
node *left,*right;
node(int x): data(x),left(NULL),right(NULL){} //构造函数
};
int maxL=0;
vector<int> level(1005,0); //初始化
void insert(node* &root, int x,int depth){
if(root == NULL){
root = new node(x);
level[depth]++;
maxL = max(depth, maxL); //之前这个地方写错了 ,这里应该取深度的最大值,而不是深度出现次数的最大值
}
else if(x > root->data ){
insert(root->right, x,depth+1);
}else{
insert(root->left, x,depth+1);
}
}
int main(){
int n,data;
node* root = NULL;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&data);
insert(root, data,0);
}
printf("%d + %d = %d\n",level[maxL],level[maxL-1],level[maxL] + level[maxL-1]);
return 0;
}
笨比版
#include<cstdio>
int n1,n2;
struct node{
int data,depth;
node *left,*right;
};
void insert(node* &root, int x){
if(root == NULL){
root = new node;
root->data = x;
root->left = root->right = NULL;
}
else if(x > root->data ){
insert(root->right, x);
}else{
insert(root->left, x);
}
}
int max=0;
void find(node* root){
if(root->left != NULL){
root->left->depth = root->depth +1;
if(root->left->depth > max) max = root->left->depth;
find(root->left);
}
if(root->right != NULL){
root->right->depth = root->depth +1;
if(root->right->depth > max) max = root->right->depth;
find(root->right);
}
}
void preorder(node* root){
if(root == NULL) return;
if(root->depth == max-1) n2++;
else if(root->depth == max) n1++;
preorder(root->left);
preorder(root->right);
}
int main(){
int n,data;
node* root = NULL;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&data);
insert(root, data);
}
root->depth = 0;
find(root);
preorder(root);
printf("%d + %d = %d\n",n1,n2,n1+n2);
return 0;
}