本文共 1085 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：给一个树的层序遍历，判断它是不是堆，是大顶堆还是小顶堆。输出这个树的后序遍历。

解题思路：

1. 借用序列已经输入好的数组，正好是完全二叉树层序遍历的下标的优势来操作比较。
2. 首先根据 a[0] 和 a[1] 的大小比较判断可能是大顶还是小顶，分别赋值 f 为 1 和 -1，先根据层序遍历，从0～(n-1)/2【所有有孩子的结点】判断他们的孩子是不是满足 f 的要求，如果有一个结点不满足，那就将 f==0 表示这不是一个堆。根据 f 输出是否是堆，大顶堆还是小顶堆，然后后序遍历，根据 id 分别遍历 id*2+1 和 id*2+2，即他们的左右孩子，遍历完左右子树后输出根结点，即完成了后序遍历。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;int n;int a[1009];void postT(int id) // 层序遍历 -> 后序遍历{    if(id>=n) return;    postT(id*2+1);    postT(id*2+2);    printf("%d%c",a[id],id==0?'\n':' '); // Ps: 这里不是 id==n-1 噢}int main(){    int k,l,r,f;    scanf("%d%d",&k,&n);    while(k--)    {        for(int i=0;i
     
      a[1]?1:-1;        for(int i=0;i<=(n-1)/2;i++)        {            l=i*2+1, r=i*2+2;            if(f==1 && (a[i]
      
       a[l] || (r
       
        a[r]))){f=0; break;}        }        if(!f) puts("Not Heap");        else printf("%s Heap\n",f==1?"Max":"Min");        postT(0);    }    return 0;}
       
      
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/81987210 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！