题目链接：点击打开链接
题目大意：给一个树的层序遍历，判断它是不是堆，是大顶堆还是小顶堆。输出这个树的后序遍历。
解题思路：
- 借用序列已经输入好的数组，正好是完全二叉树层序遍历的下标的优势来操作比较。
- 首先根据 a[0] 和 a[1] 的大小比较判断可能是大顶还是小顶，分别赋值 f 为 1 和 -1，先根据层序遍历，从0～(n-1)/2【所有有孩子的结点】判断他们的孩子是不是满足 f 的要求，如果有一个结点不满足，那就将 f==0 表示这不是一个堆。根据 f 输出是否是堆，大顶堆还是小顶堆，然后后序遍历，根据 id 分别遍历 id*2+1 和 id*2+2，即他们的左右孩子，遍历完左右子树后输出根结点，即完成了后序遍历。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using 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<n;i++) scanf("%d",&a[i]); f=a[0]>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<n && a[i]<a[r]))){f=0; break;} else if(f==-1 && (a[i]>a[l] || (r<n && a[i]>a[r]))){f=0; break;} } if(!f) puts("Not Heap"); else printf("%s Heap\n",f==1?"Max":"Min"); postT(0); } return 0; }
