pta l2-6（树的遍历）

题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456

题意：给出一个二叉树的结点数目n，后序遍历序列post，中序遍历序列in，求其层序遍历序列。

思路：首先给二叉树每个结点一个编号，按照层序遍历的顺序一次编号，即一个编号为i的结点其左子树根节点编号为2*i+1，其右子树根节点的编号为2*i+2（二叉树的根节点为0），因为30层的二叉树编号达到了2*30-1，不能直接用数组存，会爆空间。我们可以用优先队列和二元组pair来存，pair的first存结点编号，second存该结点的值。之后就暴力递归了，每次将根节点入队，然后依次对其左子树、右子树递归调用。

AC代码：

#include<bits/stdc++.h>
using namespace std;int post[35],in[35];
int n;
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > pq;void getc(int l,int r,int root,int index){if(l>r) return;int i=l;while(in[i]!=post[root]) ++i;pq.push(make_pair(index,post[root]));getc(l,i-1,root-1-r+i,2*index+1);getc(i+1,r,root-1,2*index+2);
}int main(){scanf("%d",&n);for(int i=0;i<n;++i)scanf("%d",&post[i]);for(int i=0;i<n;++i)scanf("%d",&in[i]);getc(0,n-1,n-1,0);PII p=pq.top();pq.pop();printf("%d",p.second);while(!pq.empty()){p=pq.top();pq.pop();printf(" %d",p.second);}printf("\n");return 0;
}