트리 순회 순서 변경

문제링크: 트리 순회 순서 변경

PreOrder, InOrder Tree 정보로 Post Tree를 출력하는 문제이다. 

간단한 예제를 통해 손으로 풀어본 뒤 짜면 간단하다. 

키는 P(부모)는 언제나 1개라는 점을 이용하면 된다. 

Pre:  PLR

In:    LPR

Post: LRP

Pre: 27 16  9 12 54 36 72  -> 맨 앞에 노드가 부모노드. 

In:   9  12 16 27 36 54 72  -> InOrder에서 부모노드를 찾으면, 왼쪽은 left subtree (0~P-1), 오른쪽은 right subtree(P+1~N-1).

Inorder tree에서 부모노드 위치가 결국 왼쪽 tree의 크기이다. (LSIZE = P) 

따라서 

Pre: 27 16  9 12 54 36 72  

하당 크기를 이용하여

Preorder tree에서도 left subtree (1~P)와 right subtree(P+1~N-1)를 나눌 수 있다. 나누고 나면, 맨 앞(0)은 root.. 반복된다. 

따라서 Preorder tree의  left subtree (1~P)와 Inorder tree의 left subtree (0~P-1)를 출력 후, 

Preorder tree의  right subtree(P+1~N-1)와 Inorder tree의 right subtree(P+1~N-1)를 출력 후, 

root node를 출력하면 된다. 

- 동작하게 만들기

#include <iostream>
using namespace std;
int C, N;
int PreOrder[101];
int InOrder[101];
 
int* subtree(int *arr, int s, int e) {
 
    int size = e - s + 1;
    int *newArr = (int*)malloc(sizeof(int)*size);
    for (int i = 0; i < size; i++) {
        newArr[i] = arr[s + i];
    }
    return newArr;
}
 
void solve(int *pre, int *in, int size) {
    if (size == 0)
        return;
 
    int p = 0;
    int root = pre[0];
    int* preLeft, *inLeft, *preRight, *inRight;
    for (int i = 0; i < size; i++)
        if (in[i] == root) {
            p = i;
            break;
        }
    int lsize = p;
    int rsize = size - (p+1);
 
        preLeft = subtree(pre, 1, p);
        inLeft = subtree(in, 0, p - 1);
        preRight = subtree(pre, p + 1, N - 1);
        inRight = subtree(in, p + 1, N - 1);
        
        solve(preLeft, inLeft, lsize);
        solve(preRight, inRight, rsize);
        cout << root << " ";
 
        free(preLeft);
        free(inLeft);
        free(preRight);
        free(inRight);
}
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> PreOrder[i];
        }
        for (int i = 0; i < N; i++) {
            cin >> InOrder[i];
        }
        solve(PreOrder, InOrder, N);
        cout << endl;
    }
    return 0;
}

위 코드를 좀 더 간단히 최적화할 수 있다. 

subtree의 배열을 복사해서 쓰지 않고 index를 계산해서 아래와 같이 메모리를 적게 쓰고 코드를 좀 더 간결하게 한다.

-최적화 버전

#include <iostream>
using namespace std;
int C, N;
int PreOrder[101];
int InOrder[101];
 
void solve(int preStart, int inStart, int size) {
    if (size < 1)
        return;
    int    root = PreOrder[preStart];
    if (size > 1) {
 
        int i, j;
        for (i = preStart, j = inStart; i < N; i++, j++)
            if (root == InOrder[j]) {
                break;
            }
        //lsize = j-inStart
        //rsize = size - (j+1)
        //이제 j= root위치
        //pre의 left = preStart+1, right = i+1 
        //in의 left = j-inStart, right=j+1
        int lsize = j - inStart;
        int rsize = (size + inStart) - (j + 1);
 
        solve(preStart + 1, inStart, lsize);
        solve(i + 1, j + 1, rsize);
    }
    cout << root << " ";
 
}
 
int main() {
    freopen("input.txt", "r", stdin);
    cin >> C;
    for (int c = 0; c < C; c++) {
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> PreOrder[i];
        }
        for (int i = 0; i < N; i++) {
            cin >> InOrder[i];
        }
        solve(0, 0, N);
        cout << endl;
    }
    return 0;
}