전위, 중위 순회를 알 때 후위 순회 구하는 알고리즘

http://www.crocus.co.kr/560 이 링크에서는 전위, 후위를 알 때 중위 순회를 구하는 

'트리'를 구하는 소스 코드를 올려두었었다. 

이번에는 트리를 구하지 않고

vector STL을 통해 전위, 중위 순회를 알 때 왼쪽 오른쪽을 계속해서 구분하여 바로 후위 순회를 구하는 소스 코드를 구현하였다.

이 코드의 내용은 '알고리즘 문제 해결 전략 2'에서 확인 할 수 있고,

자세한 내용은 주석을 통해 달아두었다.

이 코드를 가지고 풀 수 있는 문제는 다음과 같다.

[4256번] 트리 :: https://www.acmicpc.net/problem/4256

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

#include <iostream> #include <cstdio> #include <vector>   using namespace std;   vector<int> slice(const vector<int> &v, int a, int b) {     return vector<int>(v.begin() + a, v.begin() + b); }   // 트리의 전위 탐색 결과와 중위 탐색 결과가 주어질 때 후위 탐색 결과를 출력. void printPostOrder(const vector<int> &preorder, const vector<int> &inorder) {     // 트리에 포함된 노드 수     const int N = preorder.size();       // 전제 : 텅 빈 트리면 return;     if (preorder.empty())         return;       // 이 트리의 루트는 전위 탐색 결과로부터 알 수 있다.     const int root = preorder[0];       // 이 트리의 왼쪽 서브트리의 크기는 중위 탐색 결과에서 루트의 위치를 찾아서 알 수 있다.     int i;     for (i = 0; i < N; i++)         if (inorder[i] == root)             break;       const int L = i;       // 오른쪽 서브 트리의 크기는 N에서 왼쪽 서브트리와 루트를 빼면 된다.     const int R = N - L - 1;       // 왼쪽, 오른쪽 서브트리의 순회 결과 출력     printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));     printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));       // 후위 순회 출력     printf("%d ", root); } int main() {     int tCase;     vector<int> pre;     vector<int> in;     scanf("%d", &tCase);       while (tCase--)     {         pre.clear();         in.clear();           int n, val;         scanf("%d", &n);           for (int i = 1; i <= n; i++)         {             scanf("%d", &val);             pre.push_back(val);         }         for (int i = 1; i <= n; i++)         {             scanf("%d", &val);             in.push_back(val);         }           printPostOrder(pre, in);           printf("\n");       }       return 0; }   //                                                        If you want to see more? click here >>

Crocus