백준 2263 트리의 순회 - C++

백준 2263 : www.acmicpc.net/problem/2263

#include <iostream>
#define max 100001

using namespace std;
int n;
int temp[max], inOrder[max], postOrder[max];

void PreOrder(int inStart, int inEnd, int postStart, int postEnd){
    if(inStart > inEnd || postStart > postEnd)
        return;
    // Pre는 Root Letf Right 순
    printf("%d ", postOrder[postEnd]);
    // in에서 root가 어디인지 찾기
    int r = temp[postOrder[postEnd]];
    // 먼저 왼쪽
    // r-inStart는 트리에서 왼쪽 자식들을 의미
    PreOrder(inStart, r-1, postStart, postStart+r-inStart-1);
    // 그 다음 오른쪽
    PreOrder(r+1, inEnd, postStart+r-inStart, postEnd-1);
}

int main(){
    scanf("%d", &n);
    // in-order
    for (int i = 0; i < n; i++)
        scanf("%d", &inOrder[i]);
    // post-order
    for (int i = 0; i < n; i++)
        scanf("%d", &postOrder[i]);
    // inOrder의 값이 어느 인덱스인지 저장
    for (int i = 0; i < n; i++)
        temp[inOrder[i]] = i;

    PreOrder(0, n-1, 0, n-1);
}

---

 이전 자료구조시간이었나 이산수학시간이었나 트리 순회를 보고 깨달은게 있어서 쉽게 개념을 잡은 것 같습니다.

// 전위 순회 : Pre Order, 루트 왼쪽 오른쪽 순
// 후위 순회 : Post Order, 왼쪽 오른쪽 루트 순
// 중위 순회 : In Order, 왼쪽 루트 오른쪽 순

 여기서 주어진게 후위와 중위인데 여기서 후위 탐색에서의 마지막은 최상단 부모노드(트리의 루트)라는 개념만 잡으면 전위 순회에서 루트를 기준으로 왼쪽 오른쪽을 나눌 수 있습니다.

    // inOrder의 값이 어느 인덱스인지 저장
    for (int i = 0; i < n; i++)
        temp[inOrder[i]] = i;

 이 부분의 경우 중위 순회에서 루트가 어디에 위치하는지 쉽게 알기 위해서 만든 임시(temp) 배열로 공간복잡도를 늘리고 시간을 압도적으로 단축할 수 있습니다. 이게 없다면 루트가 어디인지 찾는 탐색 알고리즘이 이루어졌을 겁니다.

void PreOrder(int inStart, int inEnd, int postStart, int postEnd){
    if(inStart > inEnd || postStart > postEnd)
        return;
    // Pre는 Root Letf Right 순
    printf("%d ", postOrder[postEnd]);
    // in에서 root가 어디인지 찾기
    int r = temp[postOrder[postEnd]];
    // 먼저 왼쪽
    // r-inStart는 트리에서 왼쪽 자식들을 의미
    PreOrder(inStart, r-1, postStart, postStart+r-inStart-1);
    // 그 다음 오른쪽
    PreOrder(r+1, inEnd, postStart+r-inStart, postEnd-1);
}

 그리고 중위, 후위 순회의 시작과 끝을 함수에 전달해서 전위 순회를 출력합니다. 전위 순회의 경우 루트 왼쪽 오른쪽 순으로 출력을 하니 

  1. 루트 출력 (printf)

  2. 왼쪽 탐색

  3. 오른쪽 탐색

을 진행해 줬습니다. 먼저 불려진 함수가 실행 스택에서 전부 사라져야 다음 함수로 넘어가기 때문에 함수를 2개로 나누기만 해도 왼쪽과 오른쪽의 우선순위를 줄 수 있었습니다.