[Algorithm] Baekjoon 2263번 : 트리의 순회

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

2263번: 트리의 순회

int inOrder[100001];
int postOrder[100001];
int inOrderIndices[100001];
 
void getPreOrder(int inOrderStart, int inOrderEnd, int postOrderStart, int postOrderEnd)
{
    if (inOrderStart > inOrderEnd || postOrderStart > postOrderEnd)
        return;
 
 
    int rootInOrderIndex = inOrderIndices[postOrder[postOrderEnd]]; // 2
    int treeLeftSize = rootInOrderIndex - inOrderStart; // 1
    int treeRightSize = inOrderEnd - rootInOrderIndex; // 5
    int leftPostOrderEnd = postOrderStart + treeLeftSize - 1;
 
    printf("%d ", postOrder[postOrderEnd]);
 
    getPreOrder(inOrderStart, rootInOrderIndex - 1, postOrderStart, leftPostOrderEnd); // 왼쪽
    getPreOrder(rootInOrderIndex + 1, inOrderEnd, leftPostOrderEnd + 1, postOrderEnd-1); // 오른쪽
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, a;
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> a;
        inOrder[i] = a;
        inOrderIndices[inOrder[i]] = i;
    }
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> a;
        postOrder[i] = a;
    }
 
    getPreOrder(1, n, 1, n);
}

이전에 살짝 비슷한 문제를 풀었어서 규칙은 거의 바로 찾긴 했는데, 인덱스계산하는게 너무 헷갈렸어서 나중에 다시 푼 문제...

 

중위순회는 (왼,중,오) 이고 후위순회는 (왼,오,중) 이기 때문에, 주어진 트리구간의 postOrderEnd에 해당하는 인덱스의 값은 반드시 해당 트리의 루트이게 된다. (전체 트리든, 서브트리든)

 

그러면 그 루트값을 다시 중위순회에서 찾는다면, 중위순회에서의 해당 인덱스기준으로 왼쪽것들은 전부 왼쪽서브트리이고 오르쪽것들은 전부 오른쪽 서브트리이게 된다.

 

노드의 총 개수는 이미 알고있기 때문에 왼쪽서브트리의 개수와 오른쪽서브트리의 개수도 자연스럽게 알 수 있게 되는데, 다시 후위순회를 입력받은 배열 기준에서 보자면 주어진 구간의 처음부터 왼쪽서브트리의 개수(중위순회배열에서 구한)만큼이 왼쪽서브트리를 구성하는 노드이고, 바로 그다음부터 postEnd-1까지가 오르쪽서브트리를 구성하는 노드이다.

-1을 하는 이유는 주어진 구간의 후위순회배열의 끝은 항상 루트이기 때문이다.

 

설명이 좀 복잡할 뿐, 노트에다가 배열요소들을 써본다음 루트만 표시하면 바로 알 수 있다.