已知中序、后序，求先序

题目：

参考题解：

首先举例：

中序： FDBEG A CH 后序： FDGEB HC A

设递归函数名为void xian（string s1,string s2）

0. 定义 len1是中序的长度，len2是后序的长度，如果后序的长度小于等于0，return；

（例子中 len1=len2=8 ）

1. 后序的最后一个字母是先序的第一个字母，定义字符 ch=这个字母，输出这个字符；

（例子中输出A）

2. 在 中序 中 找到 字符ch 的下标，记为pos；

（例子中pos=5）

【用string的 find 函数，关于 find函数 可见这篇博客：】

3. 以pos为分界线，开始递归 中序pos 的【0，pos) 和 【pos+1，len1）；

（例子中的 左边FDBEG 和 右边CH）

对应的是 后序序列的【0，pos)部分和【pos，len2-1）；

（例子中的 左边FDGEB 和 右边HC）

这时可以用string的substr函数：

substr的参数是起点和长度，所以递归写成：xian(s1.substr(0,pos) , s2.substr(0,pos));//左

和 xian (s1.substr(pos+1,len1-pos-1),s2.substr(pos,len2-1-pos));//右

如果写法上简略一点的话，可以写成：

xian(s1, s2.substr(0,pos));和xian (s1.substr(pos+1),s2.substr(pos,len2-1-pos));

代码：

#include<bits/stdc++.h>
using namespace std;
char s1[10],s2[10];
void xian(string s1,string s2){
    int len1=s1.size();
    int len2=s2.size();
    if(len2<=0)return;
    char c=s2[len2-1];cout<<c;
    int pos=s1.find(c);
    xian(s1.substr(0,pos),s2.substr(0,pos));
    xian(s1.substr(pos+1,len1-pos-1),s2.substr(pos,len2-pos-1));
}
int main()
{
	string s1,s2;
    cin>>s1>>s2;
    xian(s1,s2);
	return 0;
 }