[백준] 2263번 : 트리의 순회 (C++)

2263번 : 트리의 순회

---

문제)

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

 

입력 :

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

 

 

 

출력 :

첫째 줄에 프리오더를 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
int n;
vector<int> post_order;
vector<int> in_order;
map<int, int> in_index_map;
 
void preorder(int in_start, int in_end, int post_index)
{
    if (in_start > in_end)
    {
        return;
    }
 
    int cur = post_order[post_index];
 
    int in_index = in_index_map[cur];
    
    cout << cur << " ";
 
    preorder(in_start, in_index - 1, post_index - in_end + in_index - 1);
    preorder(in_index + 1, in_end, post_index - 1);
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
 
    int temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        in_order.push_back(temp);
        in_index_map.insert(make_pair(temp, i));
    }
 
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        post_order.push_back(temp);
    }
 
    preorder(0, n - 1, n - 1);
 
    return 0;
}
 
//7
//4 2 1 5 3 6 7 (InOrder)
//4 2 5 7 6 3 1 (PostOrder)
 
// 위의 예시에서 
// postorder의 마지막 인자인 1이 루트노드가 되고,
// inorder의 1을 기준으로 좌측이 좌측 노드, 우측이 우측 노드가 된다.
// post노드의 1에 가장 가까운 수가 자식 노드가 된다.
// 위의 예제에서는 1의 좌측 수 (4, 2) 중 postorder에서 1에 가장 가까운
// 2가 1의 좌측 자식노드가 되고, (5, 3, 6, 7) 중 1에 가장 가까운 3이
// 1의 우측 자식 노드가 된다.
 
// 이렇게 좌측 우측으로 나누어 문제를 풀어가기 때문에 분할정복 + 트리 문제가 된다.

---

출처 : https://www.acmicpc.net/problem/2263 

2263번: 트리의 순회