백준/2263번/트리의 순회/골드1

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

문제 설명

Site: Baekjoon
Number: 2263
Category: Recursion
Rank: Gold 1

트리의 중위 순회와 후위 순회가 주어 졌을 때, 전위 순회를 출력하는 문제입니다.

문제 풀이

중위 순회와 후위 순회의 특징을 사용하여 재귀를 통해 해결하였습니다.

시작은 트리의 루트에서 시작하며 후위 순회의 가장 마지막 점이 트리의 루트입니다.

트리의 루트에서 왼쪽 첫 노드는 중위 순회와 후위 순회를 통해 확인합니다.

후위 순회에서 오른쪽 자식들의 갯수만큼 왼쪽으로 가면 왼쪽 subtree가 나오며 동일하게 마지막 점이 해당 subtree의 루트 = 왼쪽 첫 자식 노드가 됩니다. 오른쪽 자식들의 갯수 = (중위 순회에서 이전 루트의 index - 중위 순회에서 현재 루트의 index) 왼쪽 첫 자식 노드 = 후위 순회에서 현재 루트의 index - 오른쪽 자식들의 갯수 - 1;

후위 순회에서 한칸 왼쪽으로 간 값은 해당 루트의 오른쪽 첫 자식 노드가 됩니다.

이를 통해 반복적으로 왼쪽과 오른쪽을 재귀 탐색하여 전위 순회처럼 출력할 수 있습니다.

#include <iostream>
#include <map>

using namespace std;

int N;

map<int, int> inorder;
int postorder[100001];
bool check[100001];

void Preorder(int root, int postidx, int pivot)
{
    //root = root 값, postidx = postorder에서의 index, pivot 우측 기준

    if (check[root] == true)
        return;

    cout << root << " ";
    check[root] = true;

    //LEFT
    int leftidx = postidx - (pivot - inorder[root]);
    if (leftidx >= 0)
        Preorder(postorder[leftidx], leftidx, inorder[root]);

    //RIGHT
    int rightidx = postidx - 1;
    if (rightidx >= 0)
        Preorder(postorder[rightidx], rightidx, pivot);
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        inorder[num] = i;
    }

    for (int i = 0; i < N; i++)
        cin >> postorder[i];

	int root = postorder[N - 1];

    Preorder(root, N - 1, N);

    return 0;
}