洛谷-P1030 求先序排列

題目描述

給出一棵二叉樹的中序與後序排列。求出它的先序排列。
（約定樹結點用不同的大寫字母表示，長度8≤8）。

輸入格式：
2行，均為大寫字母組成的字元串，表示一棵二叉樹的中序與後序排列。
輸出格式：
1行，表示一棵二叉樹的先序。
           

思路：

1.通過後序找根節點

2.通過根節點回中序劃分左右子樹

3.重複1，2

Ps :雖然思路蠻清晰的,但是寫代碼的時候還是不斷出錯，

最後隻好去看大牛們的代碼了ORZ，用到了各種string類的函數，

也是讓我發現自己真的什麼都不懂了，繼續加油鴨。

附上自己寫的3.0版本代碼。

#include<cstdio>
#include<iostream>
#include<cstdio>
using namespace std;
void DFS(string LDR, string LRD){
	if(LDR.size()>0){
		char degree = LRD[LRD.size()-1];
		cout << degree;  //找到根節點并輸出 
		int point = LDR.find(degree);  //找到根在中序中的下标
		DFS(LDR.substr(0,point),LRD.substr(0,point));
		DFS(LDR.substr(point+1),LRD.substr(point,LRD.size()-1-point)); //遞歸尋找左右子樹 
	}
}

int main(){
	string LDR,LRD;
	cin >> LDR; cin >> LRD;
	DFS(LDR,LRD);
	cout << endl;
	return 0;
}