BOJ 2263 - Tree

요구사항

어느 트리의 인오더와 포스트오더의 출력물을 가지고 트리를 추정하여 preorder로 출력해야하는 문제이다.

접근방법

포스트오더의 맨뒤가 항상 루트노드이고 인오더는 그 루트노드를 기준으로 좌우 노드를 구분할 수 있다는 힌트를 이용해야한다.

코드흐름

재귀를 시작하기전에 주어진 인오더 노드들의 위치가 몇번째인지 인덱스를 node_index변수에 기록해둔다. 사용할 재귀함수는 4가지 인자를 받는데 아래와 같다.
1. 현재 사이클에서 인오더의 시작노드 인덱스.
2. 현재 사이클에서 인오더의 끝노드 인덱스.
3. 현재 사이클에서 포스트오더의 시작노드 인덱스.
4. 현재 사이클에서 포스트오더의 끝노드 인덱스.

재귀 종료조건은 인오더나 포스트오더의 시작인덱스가 끝노드 인덱스를 초과하면 종료하도록한다.
매 사이클마다 포스트오더 끝인덱스는 항상 루트노드이므로 이를기준으로 인오더의 좌우의 기준을 잡아 왼쪽노드 크기와 오른쪽 노드의 크기를 구한다. 그리고 왼쪽노드 사이클과 오른쪽 노드 사이클을 돌려준다.

왼쪽노드 사이클의 파라미터

1. 인오더의 시작 인덱스는 그대로 준다.
2. 인오더의 끝 인덱스는 루트노드 인덱스 직전 인덱스로 준다.
3. 포스트오더의 시작 인덱스는 그대로 준다.
4. 포스트오더의 시작위치에 앞에서 구한 루트기준 왼쪽노드사이즈를 더하는데, 이 때 포스트오더는 인오더와 다르게 루트 인덱스의 위치가 오른쪽 노드와 순서가 바뀐 맨 뒤에있기에 -1을 해준다.

오른쪽노드 사이클의 파라미터

1. 루트노드 인덱스의 다음 인덱스를 준다.
2. 인오더 끝 인덱스 그대로 준다.
3. 포스트오더 끝 인덱스에서 앞에서 구한 오른쪽노드 크기를 빼준다.
4. 포스트오더 끝 인덱스에서 -1을 해준다. 이유는 기존 끝 인덱스는 루트노드 였기 때문에.

import sys

sys.setrecursionlimit(10**9)
n = int(input())
inorder = [*map(int,input().split(' '))]
postorder = [*map(int,input().split(' '))]

node_index = dict()
for i in range(len(inorder)):
    node_index[inorder[i]] = i

def cycle(in_start, in_end, post_start, post_end):
    if in_start > in_end or post_start > post_end:
        return
    root = postorder[post_end]
    # 다음 재귀로 넘길 왼쪽 노드사이즈
    left_size = node_index[root] - in_start
    # 다음 재귀로 넘길 오른쪽 노드사이즈
    right_size = in_end - node_index[root]
    print(root, end=' ')
    # 왼쪽 사이클
    cycle(in_start, node_index[root] - 1, post_start, post_start + left_size - 1)
    # 오른쪽 사이클
    cycle(node_index[root] + 1, in_end, post_end - right_size, post_end - 1)

cycle(0, n - 1, 0, n - 1)