[C++][백준 6597] 트리 복구

문제

접근 방법

DBACEGF ABCDEFG를 살펴보면
프리오더의 D를 기준으로 인오더는 ABC EFG로 나뉘고
프리오더의 B를 기준으로 인오더는 A C로 나뉩니다.
즉 프리오더의 순서대로 존재하는 값들은 인오더를 반으로 나누는 성질을 가지고 있습니다.

이유는 프리오더가 먼저 도착한 부분은 부모 노드일 것이기 때문입니다.

프리오더의 값을 기준으로 인오더를 나누면 트리의 좌측, 우측으로 나뉜다는 점을 재귀적으로 활용하면 트리의 구조를 알 수 있습니다.

코드

#include <iostream>
using namespace std;
string preorder, inorder;
int index;

void recur(int left, int right)
{
    if (left > right)
    {
        return;
    }

    char curNode = preorder[index++];
    int curInorderIndex = inorder.find(curNode);

    recur(left, curInorderIndex - 1);
    recur(curInorderIndex + 1, right);

    cout << curNode;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    while (cin >> preorder >> inorder)
    {
        index = 0;
        recur(0, preorder.size() - 1);
        cout << "\n";
    }
    return 0;
}

풀이

프리오더의 값을 순서대로 가져와서 절반으로 나누는 재귀를 실행하면 됩니다.

포스트오더의 경우 왼쪽, 오른쪽 탐색 후 마지막에 출력을 하면 됩니다.