思路

利用后序的最后一个字符确定根，然后在中序找这个字符，然后两边二分。二分前先输出根

代码

#include <bits/stdc++.h>
using namespace std;
string zhong,hou;
void xian(int hl,int hr,int il,int ir){
	int mid = zhong.find(hou[hr]);
	cout << hou[hr];
	if (mid > il)	xian(hl,hl + (mid - il) - 1,il,mid - 1);
	if (mid < ir)	xian(hl + (mid - il),hr - 1,mid + 1,ir);
}
int main(int argc, char **argv){
	cin >> zhong >> hou;
	xian(0,hou.size() - 1,0,zhong.size() - 1);
	return 0;
}

P1030

首先，老师ppt上有反推的代码

校内

校外

适配修改地点：

1.在递归之前输出根节点

2.函数是int类型的，记得用一个int变量承接它的值

不想抄ppt看这里

#include<bits/stdc++.h>
using namespace std;
struct node{//the node of the tree
	char v;int left,right;//left sub-node,right sub-node
}tree[1000005];
int num=-1;string m,r;
int mrtol(string m,string r){
	if(r.length()==0)return -1;
	char rootChar=r[r.length()-1];//寻找根节点(hou xu bian li de zui hou yi ge)
	int pos=m.find(rootChar);//zai zhong xu bian li zhong xun zhao gen jie dian
	num++;
	int ct=num;
	cout<<rootChar;
	tree[ct].v=rootChar;
	tree[ct].left=mrtol(m.substr(0,pos),r.substr(0,pos));
	tree[ct].right=mrtol(m.substr(pos+1),r.substr(pos,r.length()-pos-1));
	return ct;	
}
int main(){
	cin>>m>>r;
	int i=mrtol(m,r);
	return /*164*/0;
}