洛谷P1030 求先序排列

那麼我們來看這道題方法：

中序ACGDBHZKX，後序CDGAHXKZB，首先可找到主根B；

那麼我們找到中序周遊中的B，由這種周遊的性質，可将中序周遊分為ACGD和HZKX兩棵子樹，

那麼對應可找到後序周遊CDGA和HXKZ（從頭找即可）

進而問題就變成求1.中序周遊ACGD，後序周遊CDGA的樹 2.中序周遊HZKX，後序周遊HXKZ的樹；

接着遞歸，按照原先方法，找到1.子根A，再分為兩棵子樹2.子根Z，再分為兩棵子樹。

就按這樣一直做下去（先輸出根，再遞歸）；

模闆概括為step1:找到根并輸出

step2:将中序，後序各分為左右兩棵子樹；

step3:遞歸，重複step1,2

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

void f(string first,string later)
{
	if(first.size()>0){
		char point;int num=0;
		point = later[later.size()-1];
		for(int i=0;i<first.size();i++){
			if(first[i]==later[later.size()-1]){
				num=i;break;
			}
		}
		cout<<point;
		f(first.substr(0,num),later.substr(0,num));
		f(first.substr(num+1),later.substr(num,later.size()-1-num));
	}
}

int main()
{
	string zhong,hou;
	cin>>zhong;
	cin>>hou;
	f(zhong,hou);
	return 0;
	
}