[트리 단계] 백준 2263번 트리의 순회

문제

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

입력

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

출력

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

 

 

후위에서는 제일 뒤에 있는것이 루트 

그것을 중위에서 찾고 그 인덱스를 기준으로 왼쪽 서브트리 오른쪽 서브트리로 구분 가능

1 2 3 4 5 6 7 8 9

(왼쪽)      (오른쪽)

후위 같은 경우는 ( 왼쪽 ) (오른쪽) (루트) 이므로 후위 시작지점에서 중위에서 찾은 왼쪽 노드 개수 만큼이 후위의 왼쪽

오른쪽 개수 만큼이 후위에서 오른쪽을 의미하므로 영역 분리 가능

 

 

 

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;

//왼쪽 루트 오른
vector<int> mid;

//왼쪽 오른 루트 
vector<int> pst;

int idx[100001];

void preOrder(int midBegin, int midEnd, int pstBegin, int pstEnd)
{
    if (midBegin > midEnd || pstBegin > pstEnd)
    {
        return;
    }

    int root = pst[pstEnd];
    cout << root << " ";

    int p = idx[root];
    int left = p - midBegin;
    preOrder(midBegin, p - 1, pstBegin, pstBegin + left - 1);
    preOrder(p + 1, midEnd, pstBegin + left, pstEnd - 1);
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        mid.push_back(x);
    }

    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        pst.push_back(x);
    }

    for (int i = 0; i < N; i++)
    {
        idx[mid[i]] = i;
    }
    preOrder(0, N - 1, 0, N - 1);
}