n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
arr[value] = index
인 배열을 하나 만들었다.#include <iostream>
using namespace std;
int n;
int inorder[100000];
int postorder[100000];
int find_idx_inorder[100001]; // +1
void divide(int inStart, int inEnd, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) return ;
int in_root_idx = find_idx_inorder[postorder[postEnd]];
int left_size = in_root_idx - inStart - 1;
cout << inorder[in_root_idx] << " ";
divide(inStart, in_root_idx-1, postStart, postStart+left_size);
divide(in_root_idx+1, inEnd, postStart+left_size+1, postEnd-1);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> inorder[i];
find_idx_inorder[inorder[i]] = i;
}
for (int i = 0; i < n; i++) {
cin >> postorder[i];
}
divide(0, n-1, 0, n-1);
return 0;
}