[백준 4256번] 트리 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

def makepost(pstart,pend,istart,iend):
  if pstart>pend:
    return
  parent = preorder[pstart]
  postorder.appendleft(parent)
  if pstart == pend:
    return
  I = Index[parent]-istart
  makepost(pstart+I+1,pend,istart+I+1,iend)
  makepost(pstart+1,pstart+I,istart,istart+I-1)

T = int(input())
for _ in range(T):
  N = int(input())
  preorder = [*map(int,input().split())]
  inorder = [*map(int,input().split())]
  Index = {}
  for i in range(N):
    Index[inorder[i]] = i
  
  postorder = deque()
  makepost(0,N-1,0,N-1)
  print(" ".join(map(str,postorder)))

 

트리의 순회 [백준 2263번] 트리의 순회 (Python3) (tistory.com) 문제와 거의 비슷한 문제이다.

트리의 순회 문제가 inorder와 postorder를 주고 preorder를 출력하라 했다면, 이 문제는 preorder와 inorder를 주고 postorder를 출력하기를 요구한다.