2020-07-14 求先序排列

题目：https://www.luogu.com.cn/problem/P1030

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 1000005
#define ll long long
#define inf 0x7fffffff
using namespace std;
string a,b;   //a是后序、b是中序。把中前遍历当做字符串输入

void pre(int x,int y,int p,int q) {//x~y为后序遍历 p~q为中序遍历
    if(x>=y||p>=q){
        if(x==y||p==q)
            cout<<a[y];
        return ;//规定边界条件
    } else {
        int i = b.find(a[y]);   //利用根左右的特性来在中序队列中查找
        cout<<a[y];//输出根
        //x+i-p
        pre( x,x+i-1-p, p,i-1 );   //递归左子树
        pre( x+i-p,y-1, i+1,q );   //递归右子树
    }
}

int main() {
    cin>>b>>a;//反一下输入
    int l = a.length()-1;//因为是0开始，所以要减一
    pre(0,l,0,l);//递归
    return 0;
}
/*
BADC
BDCA
*/