宇宙无敌牛X超强无敌保证你懂不懂来砍题解

题意
给定以中序和后序排列遍历这棵树的值，让你推导出先序遍历的值；

分析
ok，本体其实是非常简单有难度的一道题，首先，后序排列的最后一位肯定是这棵树的根节点，由此我们可以使用这个根节点来将原树拆分成两个树 然后库库拆 把每次拆的根输出就是先序排列
是不是很难理解
但是没有关系！
举个例子

这张图是一个树！它的中序排列是什么呢？

没错 是 DBEAFCG ！

那么后序排列是什么呢？

没错就是 DEBFGCA ！

根据上面的分析 我们可以知道在后序排列的最后一位 就是这棵树的根节点！
那就是 A ！
现在 我们来拆！
通过这个A 我们可以把DBEAFCG 拆成 DBE 和 FCG 两棵子树

但是后序排列的最后一位不是这两棵子树的根，该怎么办呢？
没错！竟然是后序，那么在这个中序排列中 在后序排列里靠后的肯定是根节点！
可以写两个for循环 一个从后往前遍历后序排列的树！
另外一个从前往后遍历中序排列的子树！

这时我们就可以找到 DBE 的根节点就是 B 而FCG的根节点就是 C
那我们再拆 拆成 D E F G 四棵只有一个节点的树，那么这时我们还需要拆吗？
显然是！不需要的！
那就在每次递归之前特判 如果 左边界 = 右边界 那就直接输出 不需要进行拆分！

那递归该怎么写呢？
这么写

void gvlr(int l, int r){ // 定义函数 l是左边界 r是右边界
	if(l==r){ // 特判 若l=r 直接输出
		cout << ldr[l]; // 输出
		return ; // return 防止进入for循环
	}
	
	for(int i=strlen(ldr)-1;i>=0;i--){ // 反向遍历反序排列
		for(int j=l;j<=r;j++){ // 遍历左边界到右边界 即遍历子树的每一个节点
			if(lrd[i] == ldr[j]){ // 如果相等 那么j就是根
				cout << ldr[j]; // 输出树根
				gvlr(l,j-1); // 修改边界 生成子树
				gvlr(j+1,r); // 修改边界 生成第二个子树
				return ; // 返回
			} 
			
		}
	}
}

非常简单 接下来放出AC代码：

#include<iostream>
#include<cstring>
using namespace std;

char ldr[1005];
char lrd[1005];

void gvlr(int l, int r){
	if(l==r){
		cout << ldr[l];
		return ;
	}
	
	for(int i=strlen(ldr)-1;i>=0;i--){
		for(int j=l;j<=r;j++){
			if(lrd[i] == ldr[j]){
				cout << ldr[j];
				gvlr(l,j-1);
				gvlr(j+1,r);
				return ;
			} 
			
		}
	}
}

int main(){
	cin >> ldr;
	cin >> lrd;
	gvlr(0,strlen(ldr)-1);
	return 0;
}