已知二叉树前（后）序和中序求后（前）序遍历（c++）

注：二叉树无法根据前序后序求中序，因为结果不唯一
对于二叉树生成思维不清楚的可以看看-》如何求前序后序的思路

1.已知后序中序求前序

先序：根左右 中序：左根右 后序：左右根
例：已知中序BADC，后序BDCA要求先序
先根据后序确定根节点为a，在根据根节点a将中序分为左右两个树，左边为先序的左边节点b，
直至所有左边节点遍历完,左边节点数为k-c1
然后向右遍历，重复上述 *** 作

#include
using namespace std;
const int N=203;
char cen[N],beh[N];
void dfs(int c1,int c2,int b1,int b2){
	int k;
	for(int i=0;i<c2;i++){
		if(cen[i]==beh[b2-1]){
			printf("%c",cen[i]);
			k=i;
			break; 
		}
	}
	if(k>c1)dfs(c1,k,b1,b1+k-c1);//遍历左边所有节点
	if(k+1<c2)dfs(k+1,c2,b1+k-c1,b2-1);//遍历右边所有节点
}
int main(){
	cin>>cen>>beh;
	int len=strlen(cen);
	dfs(0,len,0,len);
	return 0;
}

2.已知前序和中序求后序

先序：根左右 中序：左根右 后序：左右根
例：已知先序ABCD，中序BADC要求后序
先找到中序根节点a,右边长度为p2-k,中序右边从c1+1+k-p1开始，找到d
先根据中序确定根节点，将先序根据根边节点划分为左右两个序列，遍历右边，右边遍历完全之后遍历左边，重复上述 *** 作

注意：必须要先确定根，否则二叉树不唯一

#include
using namespace std;
const int N = 203;
char pre[N], cen[N];
string beh;
void dfs(int p1, int p2, int c1, int c2) {
	int k;
	for (int i = 0; i < c2; i++) {
		if (cen[i] == pre[p1]) {
			beh.push_back(cen[i]);//因为先找到的是根节点，而后序中根节点在最后，所以暂存
			k = i;
			break;
		}
	}
	if (k + 1 < c2)dfs(p2 - (c2 - k - 1), p2,k + 1, c2);//遍历右边所有节点
	if (k > c1)dfs(p1+1, p1+1+k-c1, c1,k);//遍历左边所有节点
}
int main()
{
	cin >> pre >> cen;
	int len = strlen(pre);
	dfs(0, len, 0, len);
	reverse(beh.begin(),beh.end());//反转字符串，得到后序
	cout<<beh;
	return 0;
}