PAT A1115 Counting Nodes in a BST （30 分）——二叉搜索树，层序遍历或者dfs

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

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

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

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.

Sample Input:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <set>
 4 #include <vector>
 5 #include <queue>
 6 using namespace std;
 7 int height;
 8 struct node{
 9     int data,h,lvl;
10     node* l,*r;
11 };
12 node* newnode(int x){
13     node* root = new node;
14     root->data=x;
15     root->l=NULL;
16     root->r=NULL;
17     root->h=1;
18     return root;
19 }
20 int geth(node* root){
21     if(root==NULL) return 0;
22     return root->h;
23 }
24 void updateh(node* root){
25     root->h = max(geth(root->l),geth(root->r))+1;
26 }
27 void insert(node* &root,int x){
28     if(root==NULL) {
29         root=newnode(x);
30         return;
31     }
32     if(x>root->data){
33         insert(root->r,x);
34         updateh(root);
35     }
36     else if(x<=root->data){
37         insert(root->l,x);
38         updateh(root);
39     }
40 }
41 int main(){
42     int n;
43     scanf("%d",&n);
44     node* root = NULL;
45     for(int i=0;i<n;i++){
46         int x;
47         scanf("%d",&x);
48         insert(root,x);
49     }
50     height=root->h;
51     int n1=0,n2=0;
52     queue<node*> q;
53     root->lvl=1;
54     q.push(root);
55     while(!q.empty()){
56         node* now=q.front();
57         q.pop();
58         //printf("%d %d
",now->data,now->lvl);
59         if(now->l!=NULL){
60             now->l->lvl=now->lvl+1;
61             q.push(now->l);
62         }
63         if(now->r!=NULL){
64             now->r->lvl=now->lvl+1;
65             q.push(now->r);
66         }
67         if(now->lvl==height)n1++;
68         if(now->lvl==height-1)n2++;
69     }
70     printf("%d + %d = %d",n1,n2,n1+n2);
71 }

View Code

注意点：二叉搜索树的建立与层序遍历。不过好像做麻烦了，用dfs会更简洁。又好像dfs都不用，可以直接在插入时候加个lvl数组算

---------------- 坚持每天学习一点点