[NOIP2001 普及组] 求先序排列

不会吧不会吧，不会有人连模板题不会做吧？那个人不会就是我吧

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 $ \le 8$）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

样例 #1

样例输入 #1

BADC
BDCA

样例输出 #1

ABCD

提示

【题目来源】
NOIP 2001 普及组第三题

#include <bits/stdc++.h>
using namespace std;
int n;
string a,b;
int find(char x){
    for(int i = 0;i<n;i++) if(a[i] == x) return i;
}
void dfs(int l1,int r1,int l2,int r2){
    int t=find(b[r2]);
    cout<<b[r2];
    if(t > l1) dfs(l1,t-1,l2,r2-r1+t-1);
    if(t < r1) dfs(t+1,r1,l2+t-l1,r2-1);
}
int main(){
	cin>>a>>b; 
	n = a.size();
    dfs(0,n-1,0,n-1);
    return 0;
}