1115 Counting Nodes in a BST （30 分）

这道题我最开始题目理解错了，最开始我理解成了统计叶子节点和叶子节点的上一层的结点数量。一提交得了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;
}