由树的中后序遍历求树的前层序遍历

题目意思言简意赅

输入：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

eg:input:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
output:4132657
注意这个树非常丑陋：
　　　　　　4
　　　　　/  
　　　　1　　　6
　　　　    / 
　　　　　3　5  7
　　　　　/
　　　　2　　　　　　　　　　

首先是先序排列:根据后序的最后一个可以找到根的位置，然后再根据根在中序里面搜索，分为左右子树

详情可以参考这篇题解https://www.luogu.org/blog/user21653/solution-p1030 这个输入输出有点区别，但原理是一样的

#include <bits/stdc++.h>
using namespace std;
const int inf=1<<30;
typedef long long ll;
typedef pair<int,int> P;
const double pi=acos(-1);
const int mod=1e8+7;
const int maxn=140;
const int maxm=6300;
int a[maxn],b[maxn];//a存后序遍历，b存中序遍历 
void rule(int i,int j,int l,int r){
    if(j-i>=0){    
    int dd=j,idx;
    cout<<a[dd];
    for(int p=l;p<=r;p++){
        if(b[p]==a[dd]){
            idx=p;break;
        }
    }
    rule(i,i+(idx-1-l),l,idx-1);
    rule(i+(idx-l),j-1,idx+1,r);
}
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    rule(1,n,1,n);
    return 0;
}

接着便是层序遍历：

输入一样，这次输出是

4 1 6 3 5 7 2
方法也基本相同，就是多了个index，初始都为-1，最后按顺序输出不为-1的
修改：注，下面这个方法虽然能过GPLT L2-006，但其实是错的，因为三十个节点的二叉树，极端情况下会变成斜的一列，那么level开10W是不够存的（最大能有2^29），正确做法应该是建树，然后BFS
参考题解：https://www.cnblogs.com/pk28/p/5496017.html

#include <bits/stdc++.h>
using namespace std;
const int inf=1<<30;
typedef long long ll;
typedef pair<int,int> P;
const double pi=acos(-1);
const int mod=1e8+7;
const int maxn=140;
const int maxm=6300;
int a[maxn],b[maxn];//a存后序遍历，b存中序遍历 
vector<int> level(100000,-1); 
void rule(int i,int j,int l,int r,int index){
    if(j-i>=0){    
    int dd=j,idx;
    level[index]=a[dd];
    for(int p=l;p<=r;p++){
        if(b[p]==a[dd]){
            idx=p;break;
        }
    }
    rule(i,i+(idx-1-l),l,idx-1,index*2+1);
    rule(i+(idx-l),j-1,idx+1,r,index*2+2);
}
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    rule(1,n,1,n,0);
    int cnt=0;
    for(int i=0;i<level.size();i++){
        if(level[i]!=-1&&cnt!=n-1){
            cnt++;printf("%d ",level[i]);
        }else if(level[i]!=-1){
            printf("%d
",level[i]);
            break;
        }
    }
    return 0;
}