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

문제

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

2263번: 트리의 순회

 

풀이

이진 트리는 루트, 왼쪽 서브트리, 오른쪽 서브트리로 나눌 수 있습니다. 
인오더와 포스트오더에서도 똑같이 3 부분으로 나눌 수 있습니다. 서브트리는 또다시 루트와 2개의 서브트리로 나눌 수 있습니다.

 

하나의 트리를 루트와 두 서브트리, 두 서브트리는 다시 루트와 서브트리로 나눌 수 있으며 이렇게 분할정복을 통해 문제를 해결할 수 있습니다.

 

예시를 들어서 구체적으로 설명해보겠습니다.

위와같은 트리가 주어졌을 때 인오더, 포스트오더에서 루트와 서브트리로 나누어보겠습니다.

루트인 1을 기준으로 왼쪽 서브트리, 오른쪽 서브트리를 나눌 수 있습니다. 

각 서브트리는 또 다시 루트와 서브트리로 나누어질 수 있습니다. 1 노드의 왼쪽 서브트리는 다시 2노드를 기준으로 왼쪽 노드와 오른쪽 노드로 나눌 수 있습니다.

 

포스트오더의 마지막 노드는 루트노드를 의미합니다. 서브트리의 루트도 서브트리의 포스트오더의 마지막 노드입니다.
포스트오더에서 루트노드의 번호를 알아내고 인오더에서 루트를 기준으로 왼쪽, 오른쪽 서브트리로 나누어 분할정복할 수 있습니다.

 

 

 

서브트리의 인오더와 포스트오더가 주어지면 이를 활용하여 루트노드를 찾고 왼쪽, 오른쪽 서브트리로 나누어 그 서브트리에 대한 재귀호출을 하는 함수를 만들어야 합니다. 

 

이때 주어진 서브트리의 루트를 리턴하여 부모 - 자식 관계를 만든 후 DFS 탐색을 통해 프리오더를 구할 수 있지만,

 

루트노드를 출력 후, 왼쪽 서브트리 재귀호출, 오른쪽 서브트리 재귀호출 순서로 처리한다면 이 순서가 프리오더와 동일합니다. 굳이 트리를 새로 만들어 저장할 필요없이 바로 출력 가능합니다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> inOrder;
vector<int> postOrder;
vector<int> inOrderIdx;

void makeTree(int inOrderStart, int postOrderStart, int length)
{
    if (length == 0)
        return; 
    
    int postRootIdx = postOrderStart + length -1;
    int root = postOrder[postRootIdx];

    int inRootIdx = inOrderIdx[root];

    int leftLength = inRootIdx - inOrderStart;
    int rightLegnth = length - leftLength - 1;

    cout << root << " ";

    makeTree(inOrderStart, postOrderStart, leftLength);
    makeTree(inRootIdx + 1, postRootIdx - rightLegnth, rightLegnth);
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n;

    inOrder.resize(n);
    inOrderIdx.resize(n+1);
    postOrder.resize(n);

    for (int i=0; i<n; ++i)
    {
        cin >> inOrder[i];
        inOrderIdx[inOrder[i]] = i;
    }

    for (int i=0; i<n; ++i)
        cin >> postOrder[i];

    makeTree(0, 0, n);
    cout << endl;
    return 0;
}