PAT甲级1115.

目录

A1115

题目

样例

输入:

9
25 30 42 16 20 20 35 -5 28

输出:

2 + 4 = 6

思路和坑点

　　思路：
　　主要的思路是先根据给出的序列建树，然后层序遍历统计每层节点个数和树的高度，这里提供两种思路解决：①为节点添加一个层数的成员变量，然后初始化根以后遍历过程中，每个节点根据父节点的层数更新自己所在的层数。②使用双指针跟踪每一层的最后一个节点，每层进行计数，每层统计结束后，更新计数数组和计数器以及层数。
　　坑点：
　　注意如何处理层数为1的情况，如果默认根为0层，则一个节点的时候需要特判。或者，根为1层，但是注意初始化每层节点个数的计数为0。

AC代码（节点存放层数信息）

#include<bits/stdc++.h>
using namespace std;
int layercnt[1003]={0};         //存放i层的个数，初始化为0，这样当最大高度为1时倒数第二层不会数组越界 
typedef struct node{            //二叉树结点
    int data;
    int layer;                  //结点所在层
    struct node *left,*right;   //节点左右指针
}Node,*Tree;
void Insert(Node* &root,int x); //将节点插入二叉树中
int layorder(Node *root);       //层序遍历获取树的高度
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    Tree root=NULL;
    scanf("%d",&n);
    for(int i=0;i<n;i++){       //读取一个数据插入树中
        int temp;
        scanf("%d",&temp);
        Insert(root,temp);
    }
    int ml=layorder(root);      //层序遍历获取树高，并按照要求输出
    printf("%d + %d = %d",layercnt[ml],layercnt[ml-1],layercnt[ml]+layercnt[ml-1]);
    return 0;    
}
void Insert(Node* &root,int x){ //插入函数
    if(root==NULL){             //空树直接初始化为根即可
        root=new Node;
        root->data=x;
        return;
    }
    if(x<=root->data){          //根据题目要求递归调用插入
        Insert(root->left,x);
    }
    else if(x>root->data){
        Insert(root->right,x);
    }
}
int layorder(Node *root){       //层序遍历算法
    int ret=0;                  //返回值，表示树的最大高度，默认高度从1开始，初始化为0
    queue<Node *> q;
    q.push(root);
    root->layer=1;              //初始化根节点高度
    while(!q.empty()){
        Node *now=q.front();
        q.pop();
        if(now->left!=NULL){
            now->left->layer=now->layer+1;
            q.push(now->left);
        }
        if(now->right!=NULL){
            now->right->layer=now->layer+1;
            q.push(now->right);
        }
        layercnt[now->layer]++;
        ret=max(ret,now->layer);//更新高度
    }
    return ret;
}

AC代码（使双指针标记层数增长）

#include<bits/stdc++.h>
using namespace std;
int layercnt[1003]={0};         //存放i层的个数，默认根为第一层，这样最大高度为1时，倒是第二层访问数组不会越界
typedef struct node{            //二叉树结点
    int data;
    struct node *left=nullptr,*right=nullptr;   //节点左右指针
}Node,*Tree;
void Insert(Node* &root,int x); //将节点插入二叉树中
int layorder(Node *root);       //层序遍历获取树的高度
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n;
    Tree root=NULL;
    scanf("%d",&n);
    if(n==1){                    //特判 
        printf("1 + 0 = 1");return 0;
    }
    for(int i=0;i<n;i++){       //读取一个数据插入树中
        int temp;
        scanf("%d",&temp);
        Insert(root,temp);
    }
    int ml=layorder(root);      //层序遍历获取树高，并按照要求输出
    printf("%d + %d = %d",layercnt[ml],layercnt[ml-1],layercnt[ml]+layercnt[ml-1]);
    return 0;    
}
void Insert(Node* &root,int x){ //插入函数
    if(root==NULL){             //空树直接初始化为根即可
        root=new Node;
        root->data=x;
        return;
    }                           //根据规则插入
    if(x<=root->data) Insert(root->left,x);
    else                 Insert(root->right,x);
}
int layorder(Node *root){       //层序遍历算法
    int layer=1,count=0;        //层数layer,每层计数器count
    Node *lastail=root,*tail=root;//lastail记录上一层的结尾，tail实时更新，一直变为本层的结尾，都初始化为根
    queue<Node *> q;
    q.push(root);
    while(!q.empty()){
        Node *now=q.front();
        q.pop();
        count++;                //本层计数
        //如果孩子不空则入队，这里tail先更新，然后顺带入队，可以写成一句，赋值时从右往左
        if(now->left!=nullptr) q.push(tail=now->left);
        if(now->right!=nullptr)q.push(tail=now->right);
        if(now==lastail){       //如果发现上一层已经统计完
            layercnt[layer++]=count;//更新计数统计，并增加层数，为下一层做准备
            count=0;            //重置计数器
            lastail=tail;       //更新lasttial为下一层的最后一个节点
        }
    }
    return layer-1;             //返回最大层数，因为最后一层统计结束后layer自动+1，所以这里要先减去
}