테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 트리 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}