1115 Counting Nodes in a BST

#include <iostream>
#include <queue>
using namespace std;
const int maxn = 1001;
int rec[maxn] = {0};	
struct node{
	int data, layer;
	node *lchild, *rchild;
};
void insert(node* &root, int x){
	if(root == NULL){
		root = new node;
		root->data = x;
		root->lchild = root->rchild = NULL;
		return;
	}
	if(x <= root->data) insert(root->lchild, x);
	else insert(root->rchild, x);
}
void levelorder(node *root){
	queue<node*> q;
	q.push(root);
	root->layer = 0;
	rec[root->layer]++;
	while(!q.empty()){
		node *front = q.front();
		q.pop();
		if(front->lchild != NULL){
			node *temp = front->lchild;
			temp->layer = front->layer + 1;
			rec[temp->layer]++;
			q.push(temp); 
		} 
		if(front->rchild != NULL){
			node *temp = front->rchild;
			temp->layer = front->layer + 1;
			rec[temp->layer]++;
			q.push(temp); 
		} 
	}
}
int main(){
	int n, num;
	cin >> n;
	node *root = NULL;
	for(int i = 0; i < n; i++){
		cin >> num;
		insert(root, num);
	}
	levelorder(root);
	int i = 0;
	while(rec[i] != 0) i++;
	printf("%d + %d = %d", rec[i - 1], rec[i - 2], rec[i - 1] + rec[i - 2]);
	return 0;
}
1115 Counting Nodes in a BST1115 Counting Nodes in a BST J_北冥有鱼 发布了146 篇原创文章 · 获赞 0 · 访问量 1252 私信 关注
上一篇:DP-01背包


下一篇:[UVA437] The Tower of Babylon