트리의 순회

• inorder, preorder, postorder의 대한 개념은 트리 (Tree) 참고

• 트리과 유사한 문제. 이 문제는 postorder와 inorder로부터 preorder을 찾고, 트리은 preorder와 inorder로부터 postorder을 찾는다.
• inorder 순회 순서는 [왼쪽 서브 트리]ROOT[오른쪽 서브 트리] 로 구성되어 있다
• postorder 순회 순서는 [왼쪽 서브 트리][오른쪽 서브 트리]ROOT 으로 구성되어 있다
• 기본 알고리즘은
  • postorder에서 가장 마지막에 방문한 노드가 ROOT이고, inorder에서 ROOT의 위치를 찾으면 그 앞부분은 왼쪽 서브 트리, 뒷 부분은 오른쪽 서브 트리가 된다.
  • 이제 구조를 다 알았으니까 preorder로 만들려면 ROOT, 왼쪽 서브 트리, 오른쪽 서브 트리 순서대로 출력하면
  • 서브 트리들을 출력하는 것은 서브 트리를 인자로 넘겨서 함수를 재귀적으로 호출하면 된다
    • 서브트리를 인자로 넘긴다고 해서, 실제로 서브트리에 대한 substring을 만들어서 넘기면 시간 및 메모리가 엄청 증가한다.
    • substring을 만들어서 넘기는 대신, substring에 해당하는 시작 인덱스와 길이만 넘기면 된다.
      • c++의 string_view 같은 것이 파이썬에도 있었다면 substring view를 넘기면 깔끔하겠지만, 그런게 없으니 어쩔수 없다
• 이렇게 하면 모든 서브 트리에 대해서 함수가 한번씩 호출되므로, 총 n번 호출된다. 노드 m개인 트리에 대해 함수가 호출되면, 트리안의 노드들을 하나씩 비교하면서 ROOT의 위치를 찾아야 하므로 O(m).
  • 최고 경우는 밸런스드 트리인 경우. 항상 왼쪽 서브트리와 오른쪽 서브트리의 크기가 똑같이 원래 트리의 크기의 1/2로 줄어들어서 전체 시간 복잡도가 O(nlogn)이 되겠지만. 최악 경우는 오른쪽으로 스큐된 트리의 경우라면 O(n^2)이 될 것이다. 퀵소트랑 비슷하니까 아마 평균도 O(nlogn)일 것 같기는 하다
  • 하지만 그냥 먼저, 모든 노드의 inorder에서 위치를 미리 다 계산해 놓으면 간단해진다. 이 전처리는 O(n)만에 끝나고, 이게 미리 계산되어있으면 함수가 한번 도는데 걸리는 시간은 O(1)이 된다. 그래서 O(n) + n*O(1) = O(n)으로 해결.
• 구현할 때는 분할정복 문제가 다들 그렇듯이 재귀로 구현하는 것이 더 직관적이기는 하다. 아래도 재귀로 구현. 재귀를 사용하지 않고 스택으로 구현하는 방식은 트리을 참고.

"""Solution code for "BOJ 2263. 트리의 순회".

- Problem link: https://www.acmicpc.net/problem/2263
- Solution link: http://www.teferi.net/ps/problems/boj/2263
"""

import sys


def solve(n, inorder, postorder, idx_by_num):
    def solve_rec(inorder_beg, postorder_beg, size):
        root = postorder[postorder_beg + size - 1]
        print(root, end=' ')
        left_tree_size = idx_by_num[root] - inorder_beg
        if left_tree_size > 0:
            solve_rec(inorder_beg, postorder_beg, left_tree_size)
        if (right_tree_size := size - left_tree_size - 1) > 0:
            solve_rec(inorder_beg + left_tree_size + 1,
                      postorder_beg + left_tree_size,
                      right_tree_size)

    solve_rec(0, 0, n)


def main():
    sys.setrecursionlimit(10**9)

    n = int(input())
    inorder = [int(x) for x in input().split()]
    postorder = [int(x) for x in input().split()]

    idx_by_num = [0] * (n + 1)
    for idx, num in enumerate(inorder):
        idx_by_num[num] = idx

    solve(n, inorder, postorder, idx_by_num)


if __name__ == '__main__':
    main()