我们使用的方法是：根据数据把堆的形状搞出来，然后我们在这个堆里找最后一个插入的点，然后我们还原这个点插入之前的情况，然后重复此过程，我们就能得到插入序列啦。
现在问题来了，如何找到最后一个插入的点呢？
阅读题目可知，新节点的插入无论如何都是往左子树插入，所以这个节点一定是在根节点一路向左的地方。
至于左右子树交换的操作，是在插入这个节点之前就进行的，所以对这个节点在左子树这个结论没有影响。
然后这个节点要么一路插到底（没儿子），要么是在某个点停下来，使原来在这里的点成为它的左子树，所以这个点一定没有右子树。
好啦，这样我们就可以找到这个点啦。
可是这个点不唯一怎么办？
假设我们找到了点u和相对点u深度更大的点v符合我们的条件。
如果点v仍然具有左子树，那么点v一定比点u先插入。因为若是点u先插入，点v再插入时，点u会和这颗树的右子树进行一次交换，就不符合给定树的形态了。
那么如果有更多点满足上面的条件，我们就选深度最小的。
如果点v没有左子树，那么谁先插入都可以，但是题目中给定的是小根堆，而我们要求方案字典序最小，那么我们认为点u先插入。
注意，我们先记录的点其实是较后插入的点，所以此时先记录点v
#include<bits/stdc++.h> using namespace std; int n,ch[100][2]/*儿子*/,fa[100],ans[100]; int rt/*根*/,del/*要删的点*/,pos/*指向的位置*/; int main(){ scanf("%d",&n); memset(ch,-1,sizeof(ch));//初始化 fa[0]=-1; for(int i=1;i<=n;i++){ int p; scanf("%d",&p); if(p<100){ ch[p][0]=i;//左儿子 fa[i]=p;//先将父亲设为自己 } else { ch[p-100][1]=i;//右儿子 fa[i]=p-100;//先将父亲设为自己 } } for(int i=0;i<=n;i++){ pos=rt;//从根开始找 del=-1;//没找到删除位置 while(del==-1){//还没找到可删的 if(ch[pos][1]==-1)//没有右儿子 del=pos; pos=ch[pos][0]; } if(ch[del][0]!=-1&&ch[ch[del][0]][0]==-1) del=ch[del][0];//字典序大的后删除 ans[i]=del; if(del==rt) rt=ch[rt][0];//此时一定没有右儿子所以直接赋值就好啦 else{ //做删除的逆向操作，把这个堆还原回去 ch[fa[del]][0]=ch[del][0]; if(ch[del][0]!=-1) fa[ch[del][0]]=fa[del]; pos=fa[del]; while(pos!=-1){ swap(ch[pos][0],ch[pos][1]); pos=fa[pos]; } } } for(int i=n;i>=0;i--) printf("%d ",ans[i]); }