PAT 1115 Counting Nodes in a BST[构建BST]

1115 Counting Nodes in a BST（30 分）

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

题目大意：根据输入构建一棵二叉搜索树，并且计算最底层的两层共有多少个节点；n1是最底层的，n2是倒数第二层的。

//做的时候就有一个问题，如果这个二叉树只有一个根节点那怎么办呢?那么n2就是0了吗?

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

struct Node{
   int data,level;
   Node* left;
   Node *right;
};
int last=0;
int no=0,no2=0;
void build(Node * &root,int data){
    if(root==NULL){
        root=new Node();
        root->data=data;
        root->left=NULL;
        root->right=NULL;
        return ;
    }
    if(data<root->data)build(root->left,data);
    else build(root->right,data);
}
void dfs(Node *root,int level){
    if(level>last)last=level;
    root->level=level;
    if(root->left!=NULL)dfs(root->left,level+1);
    if(root->right!=NULL) dfs(root->right,level+1);
}

void dfs2(Node* root){
    if(root->level==last)no++;
    else if(root->level==last-1)no2++;
    if(root->left!=NULL)dfs2(root->left);
    if(root->right!=NULL) dfs2(root->right);
}
int main() {
    int n;
    cin>>n;
    int temp;
    Node* root=NULL;
    for(int i=0;i<n;i++){
        cin>>temp;
        //cout<<"oooo";
        build(root,temp);
    }
    //if(root==NULL)cout<<"jjj";
    dfs(root,0);
    dfs2(root);
    cout<<no<<" + "<<no2<<" = "<<no+no2;
    return 0;
}

View Code

//第一次提交的时候这样，0，2，6三个测试点都没过，都是答案错误，只得了8分。。

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

struct Node{
   int data,level;
   Node* left;
   Node *right;
};
int last=0;
int no=0,no2=0;
void build(Node * &root,int data){
    if(root==NULL){
        root=new Node();
        root->data=data;
        root->left=NULL;
        root->right=NULL;
        return ;
    }
    if(data<=root->data)build(root->left,data);
    else build(root->right,data);
}
void dfs(Node *root,int level){
    if(level>last)last=level;
    root->level=level;
    if(root->left!=NULL)dfs(root->left,level+1);
    if(root->right!=NULL) dfs(root->right,level+1);
}

void dfs2(Node* root){
    if(root->level==last)no++;
    else if(root->level==last-1)no2++;
    if(root->left!=NULL)dfs2(root->left);
    if(root->right!=NULL) dfs2(root->right);
}
int main() {
    int n;
    cin>>n;
    int temp;
    Node* root=NULL;
    for(int i=0;i<n;i++){
        cin>>temp;
        //cout<<"oooo";
        build(root,temp);
    }
    //if(root==NULL)cout<<"jjj";
    dfs(root,0);
    dfs2(root);
    cout<<no<<" + "<<no2<<" = "<<no+no2;
    return 0;
}

//查看了被人的题解之后发现是因为，我弄错了BST的定义。

小于等于当前节点的都放到左子树！