题目

PAT 甲级 1020 Tree Traversals (25分) 中序后序转层序

思路

1 后序确定根，中序确定左右子树，递归处理，记录二叉树若静态存储时的索引（从0开始，父为i，左子为2*i+1，右子为2*i+2） 2 索引从小到大对结点进行排序，即为层序序列

题解

#include <iostream> #include <vector> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 40; struct Node{ int d; //结点元素值 int l; //层级 }; int in[maxn],post[maxn]; vector<Node> pre; void pre_order(int in[],int post[],int il,int ir,int pl,int pr,int index){ if(il>ir)return; //后序最后一个元素将中序序列分为左右子树 int root = post[pr]; pre.push_back({root,index}); // 中序中找到根结点位置 int k=il; while(k<ir&&in[k]!=root)k++; // 递归分治 pre_order(in,post, il, k-1, pl, pl+k-il-1, 2*index+1); pre_order(in,post, k+1, ir, pl+k-il, pr-1, 2*index+2); } bool cmp(Node &n1,Node &n2){ return n1.l<n2.l; } int main(int argc,char * argv[]){ int n; 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]); } pre_order(in,post,0,n-1,0,n-1,0); sort(pre.begin(),pre.end(),cmp); printf("%d",pre[0].d); for(int i=1;i<n;i++){ printf(" %d",pre[i].d); } return 0; }