[c++] 백준 #2263 트리의 순회

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

<풀이 방법>

한참을 이게 왜 분할정복 문제인지 고민하면서 보다가 post order의 속성을 이용하면 된다는 것을 깨달았다. 그것이 큐이다! post order의 경우 left right root 순으로 읽기 때문에 post order를 거꾸로 읽으면 root에서부터 root -> right -> left 순이 된다. 즉, post order에서 뒤에서부터 값을 읽으면 root가 무엇인 지 알 수 있고, 이를 통해 in order로 받은 input을 root를 기준으로 그래프를 left와 right로 나눌 수 있다.(분할정복의 의미) 

나는 문제를 풀 때 in order와 post order를 보고 그래프가 어떻게 생겼는지 유추하고 나서(...), pre order 순으로 정렬하면 되겠지?하면서 비교적 복잡하게 생각하고 코드를 짰는데, 이후 다른 사람들의 코드를 좀 구경해보니 그냥 post order를 거꾸로 읽은 후 그 자리에서 root -> left -> right를 읽어서 pre order로 출력을 하는 것을 봤다. 나란 녀석.. 역시 비효율적이지만 뭐 어때! 채점에서 통과했으면 됬지 뭐! :>

#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
#include <string.h>
#include <cstdio>
#include <math.h>
#include <map>
#include <algorithm>
#include <queue>
#include <stack>
#include <utility>
using namespace std;
 
struct node
{
    int data;
    node* left;
    node* right;
};
 
int N;
vector<int> inorder;
stack<int> postorder;
struct node TREE[100001];
int position[100001];
 
// root -> right -> left visit
void conquer(int root, int start, int end)
{
    int dist = position[root];
    if (dist != end)
    {
        int n_right = postorder.top();
        postorder.pop();
        TREE[root].right = &TREE[n_right];
        conquer(n_right, dist+1, end);
    }
    if (dist != start)
    {
        int n_left = postorder.top();
        postorder.pop();
        TREE[root].left = &TREE[n_left];
        conquer(n_left, start, dist-1);
    }
}
 
void preorder(node x) // root, left, right
{
    cout << x.data << " ";
    if (x.left != NULL) preorder(*x.left);
    if (x.right != NULL) preorder(*x.right);
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    int val;
    for (int i = 0; i < N; i++)
    {
        cin >> val;
        inorder.push_back(val);
        TREE[val].data = val;
    }
 
    for (int i = 0; i < N; i++)
    {
        cin >> val;
        postorder.push(val);
    }
 
    
    for (int i = 0; i < N; i++)
    {
        position[inorder[i]] = i;
    }
 
    int root = postorder.top();
    postorder.pop();
    
    conquer(root, 0, N-1);
    preorder(TREE[root]);
 
    return 0;
}