前順遍歴と中順遍歴から後順遍歴(C+)を求める
1187 ワード
題意は大体文字列の形式で前序遍歴と中序遍歴を入力し、後序遍歴を出力する.一つ栗↓入力:ABDEC DBEAC出力:DEBCA
#include
#include
using namespace std;
void findPostorder(string preorder, int low_1, int high_1, string inorder, int low_2, int high_2, char* postorder, int low_3, int high_3) {
if (low_1 == high_1) {
postorder[high_3] = preorder[low_1];
return;
}
int i;
for (i = low_2; i <= high_2; i++) {
if (preorder[low_1] == inorder[i]) {
break;
}
}
postorder[high_3] = preorder[low_1];
findPostorder(preorder, low_1 + 1, low_1 + i, inorder, low_2, low_2 + i - 1, postorder, low_3, low_3 + i - 1);
findPostorder(preorder, low_1 + i + 1, high_1, inorder, low_2 + i + 1, high_2, postorder, low_3 + i, high_3 - 1);
}
int main() {
string preorder, inorder;
cin >> preorder >> inorder;
int length = preorder.size();
char postorder[length];
//
findPostorder(preorder, 0, length - 1, inorder, 0, length - 1, postorder, 0, length - 1);
for (int i = 0; i < length; i++) {
cout << postorder[i];
}
return 0;
}