트리

• 트리의 순회과 유사한 문제. 이 문제는 preorder와 inorder로부터 postorder을 찾고, 트리의 순회은 postorder와 inorder로부터 preorder을 찾는다. 풀이의 아이디어는 거의 동일하므로 그쪽을 참고.
• 구현은 트리의 순회과 살짝 다르게 했다. 트리의 순회에서는 재귀로 구현했지만, 여기에서는 비재귀로 구현해봤다. 재귀 코드가 필요하면 트리의 순회을 참고.

"""Solution code for "BOJ 4256. 트리".

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

Tags: [DnC]
"""


def main():
    T = int(input())
    for _ in range(T):
        n = int(input())
        preorder = input().split()
        inorder = input().split()

        preorder_iter = iter(preorder)
        inorder_pos_by_node = {node: pos for pos, node in enumerate(inorder)}
        answer = []
        stack = [(0, n)]
        while stack:
            top = stack.pop()
            if isinstance(top, str):
                answer.append(top)
                continue
            beg, end = top
            root = next(preorder_iter)
            root_pos_in_inorder = inorder_pos_by_node[root]
            stack.append(root)
            if root_pos_in_inorder + 1 < end:
                stack.append((root_pos_in_inorder + 1, end))
            if beg < root_pos_in_inorder:
                stack.append((beg, root_pos_in_inorder))

        print(' '.join(answer))


if __name__ == '__main__':
    main()