https://www.acmicpc.net/problem/5639
입력값은 전위 순회 결과이므로 루트-왼쪽-오른쪽 순서이다. 그리고 이 트리는 이진 검색 트리이다.
즉, 첫번째 값은 루트이고, 루트보다 작은 왼쪽 서브트리의 값들이 나열되고, 루트보다 큰 오른쪽 값들이 나열된다.
루트보다 큰 값을 가지는 최초 노드의 인덱스를 greater에 저장하고, greater 이전과 이후로 나누어 후위 순회를 실행하였다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> tree;
void postOrder(int left, int right) {
if(left > right) return;
int root = tree[left];
int greater = left+1;
for(int i=left+1; i<=right; i++) {
if(tree[i] > root) {
greater = i;
break;
}
}
postOrder(left+1, greater-1);
postOrder(greater, right);
cout << root << "\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int value;
while(cin >> value) {
tree.push_back(value);
}
postOrder(0, tree.size()-1);
return 0;
}