洛谷——P1030 求先序排列

https://www.luogu.org/problem/show?pid=1030#sub

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入输出格式

输入格式：

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

输出格式：

1行，表示一棵二叉树的先序。

输入输出样例

输入样例#1：

BADC
BDCA

输出样例#1：

ABCD

#include <algorithm>
#include <cstring>
#include <cstdio>

#define N 10015

using namespace std;

char midx[N],bhdx[N];
char midd[N],bhdd[N];

void DFS(int l,int r,int L,int R)
{
    printf("%c",bhdx[R]);
    if(bhdd[R]>l) DFS(l,bhdd[R]-1,L,bhdd[R]-l+L-1);
    if(bhdd[R]<r) DFS(bhdd[R]+1,r,R-(r-bhdd[R]),R-1);
}

int main()
{
    scanf("%s",midx);
    scanf("%s",bhdx);
    int n=strlen(midx);
    for(int i=0;i<n;i++) midd[midx[i]]=i;
    for(int i=0;i<n;i++) bhdd[i]=midd[bhdx[i]];
    DFS(0,n-1,0,n-1);
    return 0;
}