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를 출력하기를 요구한다.