코드

#include <iostream>
using namespace std;
int inorder[100001];
int postorder[100001];
int idx[100001];
void preorder(int inbegin, int inend, int postbegin, int postend)
{
    if (inbegin > inend)
        return;
    if (postbegin > postend)
        return;
    int root = postorder[postend];
    cout << root << " ";
    // 왼쪽
    preorder(inbegin, idx[root] - 1, postbegin, postbegin + idx[root] - inbegin - 1);
    // 오른쪽
    preorder(idx[root] + 1, inend, postbegin + idx[root] - inbegin, postend - 1);
}
int main(void)
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> inorder[i];
        idx[inorder[i]] = i;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> postorder[i];
    }
    preorder(0, n - 1, 0, n - 1);
    return 0;
}

문제 접근

트리 pre, post, inorder 방식의 흐름을 직접 그려가며 코드를 작성한다.

해결 방법

preorder 방식은 루트 -> 왼 -> 오 를 탐구하는 방식이다.
inoder 방식은 왼 -> 루트 -> 오 를 탐구하는 방식이다.
postorder 방식은 왼 -> 오 -> 루트를 탐구하는 방식이다.
postorder 방식에서 맨 마지막원소는 루트를 의미한다.

1. 첫, 둘 매개변수 -> inorder , 3,4 번째 매개변수 -> postorder
2. root 출력 ( inorder 방식)
3. idx 배열을 통해 루트가 어디에 위치하는지 파악 -> 왼쪽의 크기 얼마정도 인지 파악.
4. 새롭게 계산된 inorder , postorder의 왼오 매개변수 넘겨줌.

기억해야 하는 것

• 재귀 함수의 흐름.
  postorder , inorder 흐름을 고려하여 매개 변수로 넘겨줌
• inorder 로 입력 받는 방식.
  idx 에 각 노드 번호의 순서를 저장해서, 루트 노드가 어느 순서에 있는 지 알게 함. 이를 통해 왼쪽, 오른쪽에 노드들의 크기를 알 수 있게함.

참고

너무 어려워서 자료를 참고했다. 나는 재귀가 너무 약한거같다...,,,,,

https://jaimemin.tistory.com/1156