[Today I Learned 07] 2. 백준(#2263)

트리 순회에 대해 공부하던 도중 중위 순회와 후위 순회의 값을 주고 전위 순회로 바꾸는 문제를 마주 했다. 트리 순회에 대해서 다 이해했다고 생각했는데 막상 문제를 마주하니깐 어떻게 풀어야 될지 감이 잡히지 않았다. 그래서 답을 보고 이해한 대로 작성해보려고 한다.

1. 트리 순회(#2263)

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

접근 방법
1. 후위 순회 값의 마지막 숫자는 전체 루트이다.
2. 중위 순회는 왼쪽, 루트, 오른쪽 순으로 작성되기 때문에 후위 순회에서 찾은 루트 값을 이용해서 왼쪽 트리와 오른쪽 트리의 노드 수를 구할 수 있다.
3. 찾은 왼쪽 노드 수와 오른쪽 노드 수를 이용하여 중위 순회를 왼쪽 트리, 루트, 오른쪽 트리로 나눌 수 있다.
4. 동일하게 후위 순회를 왼쪽 트리, 오른쪽 트리, 루트로 나눌수 있다.
5. 이러한 과정을 재귀로 반복한다.

from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
input = stdin.readline

# 노드 개수
n = int(input())
# 중위 순회 결과 값
inorder = list(map(int, input().split()))
# 후위 순회 결과 값
postorder = list(map(int, input().split()))
# 중위 순회 각 노드 인덱스 
index = [0] * (n + 1)
for i in range(n):
    index[inorder[i]] = i
    
# 전위 순회로 바꾸는 함수
def preorderset(inStart, inEnd, poStart, poEnd):
    if inStart > inEnd or poStart > poEnd: return
    
    # 트리의 루트
    root = postorder[poEnd]
    # 루트의 인덱스
    root_idx = index[root]
    # 전위 순회는 '루트-왼쪽-오른쪽'이기 때문에 바로 루트 출력
    print(root, end=' ')
    
    # 왼쪽 노드 개수
    left = root_idx - inStart
    # 오른쪽 노드 개수
    right = inEnd - root_idx
    
    # 왼쪽 트리 재귀
    preorderset(inStart, root_idx - 1, poStart, poStart + left - 1)
    # 오른쪽 트리 재귀
    preorderset(root_idx + 1, inEnd, poEnd - right, poEnd - 1)

preorderset(0, n - 1, 0, n - 1)