PAT (Advanced Level) Practice 1115 Counting Nodes in a BST

深藏阁楼爱情的钟 2023-07-03 07:28 20阅读 0赞

1、建二叉排序树

2、层序遍历，我是把每层的节点数记录下来，最后输出倒数两个

ps：当n=1时，输出“1 + 0 = 1”

#include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    struct node{
        node* lchild;
        node* rchild;
        int data,layer;
    };
    void insertNode(int n,node* &root){
        if(root==NULL){
            root = new node;
            root->lchild=NULL;
            root->rchild=NULL;
            root->data=n;
            return;
        }
        if(n<=root->data){
            insertNode(n,root->lchild);
        }else{
            insertNode(n,root->rchild);
        }
    }
    
    vector<int> v;
    void layerTravel(node* root){
        int layer=0,num=0;
        queue<node*> q;
        root->layer=layer;
        q.push(root);
        while(!q.empty()){
            node* Node = q.front();
            q.pop();
            if(Node->lchild!=NULL){
                Node->lchild->layer=Node->layer+1;
                q.push(Node->lchild);
            }
            if(Node->rchild!=NULL){
                Node->rchild->layer=Node->layer+1;
                q.push(Node->rchild);
            }
            if(Node->layer!=layer){
                v.push_back(num);
                num=0;
                layer=Node->layer;
            }
            num++;
        }
        v.push_back(num);
    }
    int main()
    {
        int n;
        cin>>n;
        node* root=NULL;
        for(int i=0;i<n;i++){
            int m;
            cin>>m;
            insertNode(m,root);
        }
        layerTravel(root);
        if(v.size()>=2){
            cout<<v[v.size()-1]<<" + "<<v[v.size()-2]<<" = "<<v[v.size()-1]+v[v.size()-2];
        }else{
            cout<<"1 + 0 = 1";
        }
        return 0;
    }