【题解】前序中序转后序

题目描述
有一棵二叉树，结点数量不超过 26，树上的每个结点都可以用一个唯一的大写英文字母区分，给定这棵二叉树的前序遍历与中序遍历，请输出它的后序遍历。

输入格式
第一行：一个字符串，表示二叉树的前序遍历；
第二行：一个字符串，表示二叉树的中序遍历。

输出格式
单独一行：一个字符串，表示二叉树的后序遍历。

数据范围
设二叉树的结点数量为 n，

对于 50% 的数据，1≤n≤10
对于 100% 的数据，1≤n≤26
样例数据
输入:
ACE
CAE
输出:
CEA
【题解】
递归分解字符串的过程。
首先，先序的首字母是数根。
其次，通过根将中序分解为，左子树部分和右子树，确定左子树节点数量和右子树节点数量。
再次，用同样的方法，递归分解左右子树。
递归调用后再输出根节点。即可得到该二叉树后续遍历的结果。
【实现代码】

#include <bits/stdc++.h>
using namespace std;
string s1,s2;//s1前序 s2中序
void build(int l1,int r1,int l2,int r2){//build(前序开始位置,前序结束位置,中序开始位置,中序结束位置)
	int m=s2.find(s1[l1]);//前序开始位置为数根  找到数根在s2中的位置m
	if(m>l2) build(l1+1,l1+m-l2,l2,m-1);//如果有左子树 根据m位置 分割出左子树并递归 
	if(m<r2) build(l1+m-l2+1,r1,m+1,r2);//如果有右子树 根据m位置 分割出右子树并递归
	cout<<s1[l1];//在归的过程中输出根
}
int main()
{
	cin>>s1>>s2;
	build(0,s1.length()-1,0,s2.length()-1);
	return 0;
}