1115. Counting Nodes in a BST (30)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following PRoperties:

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

925 30 42 16 20 20 35 -5 28Sample Output:
2 + 4 = 6
#include<cstdio>#include<algorithm>#include<queue>using namespace std;struct Node{	int data;	int depth;	Node *l, *r;	Node(int x):data(x),l(NULL),r(NULL){}}*root;void insert(Node*&root,int x)//这个地方要用引用{	if (root == NULL)	{		root = new Node(x);		return;	}	else if (x <= root->data)	{		insert(root->l, x);	}	else		insert(root->r, x);}int maxdepth = -1;void dfs(Node*root, int depth){	if (!root)	{		maxdepth = max(maxdepth, depth);		return;	}	dfs(root->l, depth + 1);	dfs(root->r, depth + 1);}int sum1, sum2;void levelorder(Node*root){	queue<Node*> Q;	Q.push(root);	root->depth = 1;	if (root->depth == maxdepth)	{		sum2++; sum1 = 0;	}	while (!Q.empty())	{		Node*f = Q.front();		Q.pop();		if (f->l)		{			Q.push(f->l);			f->l->depth = f->depth + 1;			if (f->l->depth == maxdepth - 1)			{				sum1++;			}			else if (f->l->depth == maxdepth)			{				sum2++;			}		}		if (f->r)		{			Q.push(f->r);			f->r->depth = f->depth + 1;			if (f->r->depth == maxdepth - 1)			{				sum1++;			}			else if (f->r->depth == maxdepth)			{				sum2++;			}		}	}}int main(){	int n;	scanf("%d", &n);	int x;	for (int i = 0; i < n; i++)	{		scanf("%d", &x);		insert(root, x);	}	dfs(root, 0);	levelorder(root);	printf("%d + %d = %d/n", sum2, sum1, sum1 + sum2);	return 0;}