[5639번] 이진 검색 트리

문제 출처 :

https://www.acmicpc.net/problem/5639

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이진 탐색 트리 :: http://www.crocus.co.kr/search/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89%20%ED%8A%B8%EB%A6%AC

2. 순회 :: http://www.crocus.co.kr/632

3. Map STL :: http://www.crocus.co.kr/604

전위, 중위를 알 때 후위를 구하는 방식은 위의 링크에서 확인 할 수 있다.

이진 탐색 트리에서 입력으로 전위 순회가 주어진다면 중위 순회는 공짜로 받을 수 있다.

왜냐면 map이 정렬 자체를 이진 탐색 트리의 구성으로 해주기 때문이다.

이렇게 전위, 중위를 알게될 때 후위를 구하는 코드를 통해 쉽게 해결할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
 
using namespace std;
 
map<int, int> m;
 
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();
 
    if (preorder.empty())
        return;
 
    // preorder[0] 항상 root
    const int root = preorder[0];
    
    int L;
    
    for (int i = 0; i < N; i++)
        if (inorder[i] == root)
        {
            L = i;
            break;
        }
 
    printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
    printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
 
    // 후위 순회 출력
    printf("%d\n", root);
}
 
int main()
{
    int val;  
    vector<int> pre;
    vector<int> in;
 
    while (scanf("%d", &val) != EOF)
    {
        m[val] = 1; // map -> 이진 탐색 트리 즉, 중위 순회에 이용
        pre.push_back(val); // 전위 순회
    }
 
    for (auto it = m.begin(); it != m.end(); it++)
        in.push_back(it->first); // 중위 순회 push
 
    printPostOrder(pre, in);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>