https://www.luogu.com.cn/problem/P1827
题目大意:
已知前序中序遍历
求后序遍历。
输入 #1
ABEDFCHG
CBADEFGH
输出 #1
AEFDBHGC
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18;
const LL N=200200,M=2002;
string a,b;
void dfs(int l1,int r1,int l2,int r2)
{
if(l1>r1||l2>r2) return ;//如果超过了界限,说明已经跑完了,可以返回去了
for(int i=l1;i<=r1;i++)//中序遍历从左到右
{
if(a[i]==b[l2])//找到根节点
{
dfs(l1,i-1,l2+1,l2+i-l1);//递归左子树
dfs(i+1,r1,l2+i-l1+1,r2);//递归右子树
cout<<a[i];
}
}
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
//给定前序中序遍历,求后序遍历
cin>>a>>b;
int l=a.size();
dfs(0,l-1,0,l-1);//全树区间,前序遍历从左到右,中序遍历从左到右
}
return 0;
}
标签:遍历,洛谷,后序,int,前序,American,USACO3.4,P1827,中序
From: https://www.cnblogs.com/Vivian-0918/p/16754460.html