题目链接：https://www.patest.cn/contests/gplt/L2-006
题意：由二叉树的后序和中序求层次遍历。
二叉树的还原：用先序或后序的顺序递归中序来建树。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <vector> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define FOR(i,k,n) for(int i=k;i<n;i++) #define FORR(i,k,n) for(int i=k;i<=n;i++) #define scan(a) scanf("%d",&a) #define scann(a,b) scanf("%d%d",&a,&b) #define scannn(a,b,c) scanf("%d%d%d",&a,&b,&c) #define mst(a,n) memset(a,n,sizeof(a)) #define ll long long #define N 105 #define mod 1000000007 #define INF 0x3f3f3f3f const double eps=1e-8; const double pi=acos(-1.0); struct node { int l,r; node() { l=r=0; } }tree[N]; queue<int> q; int postorder[N],inorder[N]; int post; int n; void build(int root,int l,int r) { int i=r; for(;i>=l;i--) { if(inorder[i]==postorder[post]) break; } if(i<r) { tree[root].r=postorder[--post]; build(tree[root].r,i+1,r); } if(i>l) { tree[root].l=postorder[--post]; build(tree[root].l,l,i-1); } } void Bfs(int root) { while(!q.empty()) q.pop(); int cnt=0; cnt++; printf("%d%c",root,cnt==n?'\n':' '); q.push(root); while(!q.empty()) { int cur=q.front(); q.pop(); if(tree[cur].l) cnt++,printf("%d%c",tree[cur].l,cnt==n?'\n':' '),q.push(tree[cur].l); if(tree[cur].r) cnt++,printf("%d%c",tree[cur].r,cnt==n?'\n':' '),q.push(tree[cur].r); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(~scan(n)) { mst(tree,0); post=n-1; FOR(i,0,n) scan(postorder[i]); FOR(i,0,n) scan(inorder[i]); int root=postorder[n-1]; build(root,0,n-1); Bfs(root); } return 0; }