[백준] 6597 - 트리 복구

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

6597번: 트리 복구

 

트리의 순회 중, preorder와 inorder을 통해서 postorder를 구하는 문제이다.

                                               D
                                              / \
                                             /   \
                                            B     E
                                           / \     \
                                          /   \     \
                                         A     C     G
                                                    /
                                                   /
                                                  F

 

 

이 입력 1의 preorder와 inorder를 보면,

preorder: DBACEGF

inorder: ABCDEFG

인데, preorder의 각 정점과 inorder의 해당 정점의 위치를 잘 살펴보자.

 

먼저 최 상위 루트인 D를 보면

DBACEGF

ABCDEFG

이다. 그런데 D의 왼쪽 서브트리는 A, B, C이고 오른쪽 서브트리는 E, G, F이다.

 

다음 B를 보면

DBACEGF

ABCDEFG

B의 왼쪽 서브트리는 A이고 오른쪽 서브트리는 C이다.

 

즉, preorder의 정점을 순서대로 읽으면 inorder는 해당 정점을 루트로 삼고, 왼쪽 오른쪽이 서브트리를 나타내는 것을 알 수 있다.

따라서 preorder를 순서대로 읽어서 해당 정점을 찾고, 왼쪽 서브트리, 오른쪽 서브트리, 출력 순으로 구현하면 postorder를 구현할 수 있다.

 

 

#include <iostream>
#include <vector>
using namespace std;

string s1, s2;
int idx = 0;

void go(int left, int right) {
    if (left > right) {
        idx--;
        return;
    }
    for (int i = 0; i < s2.length(); i++) {
        if (s1[idx] == s2[i]) {
            idx++;
            go(left, i - 1);
            idx++;
            go(i + 1, right);
            cout << s2[i];
            return;
        }
    }
}

int main() {
    while (1) {
        cin >> s1;
        if (cin.eof()) {
            break;
        }
        cin >> s2;
        idx = 0;
        go(0, s1.length() - 1);
        cout << "\n";
    }
}