[BOJ] 트리_4256 C++ 풀이

문제

하나의 이진 트리를 전위, 중위 순회한 결과가 주여졌을때 후위 순회를 했을때의 결과를 구하는 문제이다. 입력으로는 테스트 케이스의 개수 $($tc), 노드의 개수$($n), 그리고 전위, 중위 순회한 결과가 주어진다.

접근 방법

입력으로 주어진 중위 순회 결과를 통해서 각 노드의 순서와 왼쪽, 오른쪽 서브트리에 존재하는 노드를 알 수 있다.

전위 순회 결과를 통해서는 다음과 같은 규칙을 찾을 수 있다. 전위 순회 결과값 배열의 인덱스 + 1을 하면 이는 곧 왼쪽 서브 트리의 루트를 가리키는 것을 의미한다.

예를 들어 arr[] = {3, 6, 5, 4, 8, 7, 1, 2} 인 전위순회 결과 배열에서 root == 3, index = 0 이고 인덱스 + 1을 하여 왼쪽 서브 트리로 이동하면 root == 6, index = 1 이 된다.

그리고 오른쪽 서브트리로 이동하는 방법은 왼쪽 서브 트리의 크기 + 1 만큼 인덱스에 더해주면 된다는 것을 찾아 낼 수 있다. root == 3, index = 0 root == 7, index = 0 + 4 + 1 == 5

구현

#include<iostream>
using namespace std;

int preNode[1001];
int inNode[1001];

void postOrder(int i, int l, int r)
{
    if(l>r) return;
    if(l==r)
    {
        cout<<preNode[i]<<' ';
        return;
    }
    int tmp = inNode[preNode[i]];
    postOrder(i+1, l, tmp-1); // left sub tree
    postOrder(i+tmp-l+1, tmp+1, r); // right sub tree
    cout<<preNode[i]<<' ';
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int tc, n, temp;

    cin>>tc;
    while(tc--)
    {
        cin>>n;

        for(int i=1; i<=n; i++) cin>>preNode[i];
        for(int i=1; i<=n; i++)
        {
            cin>>temp;
            inNode[temp]=i;
        }

        postOrder(1,1,n);
        cout<<'\n';
    }
    
    return 0;
}

BOJ_트리