[PS | 한 번에 맞자!] 백준 4256

0. 문제

트리

4256번: 트리

---

1. 문제 생각

전위순회, 중위순회, 후위순회의 핵심은 규칙과 재귀이다.
재귀에서도 사실상 어디에서 재귀로 진입하는가(반환하는가) 가 가장 중요하다. -> 기초 설명

위 문제에서도 전위, 중위 순회일 떄 규칙적으로 왼쪽/오른쪽으로 빠지는 것이 규칙적으로 진행됨을 알 수 있다.
따라서 recursion을 전위, 중위 순회에 따라 root 노드 -> left 노드 -> right 노드로 들어가도록 구현하고

if (currentNode){
Visit(currentNode);
Postorder(currentNode -> leftChild);
Postorder(currentNode -> rightChild);
	Visit(currentNode);
}

그 후 우리는 후위 순회를 구현할 것이므로 위의 함수처럼 맨 나중에 node를 visit하면 된다.

---

2. 문제 구현

import sys
input = sys.stdin.readline

def recursion(preorder, inorder):
    
    if not preorder:
        return

    node = preorder[0]
    idx = inorder.index(node)
	# 전위순회를 반환해야 하면 여기에서 print
    recursion(preorder[1:idx+1], inorder[:idx])
	# 중위순회를 반환해야 하면 여기에서 print
    recursion(preorder[idx+1:], inorder[idx+1:])
    # 후위순회를 반환해야 하면 여기에서 print
    print(node, end=' ')

t=int(input())
for _ in range(t):
    n=int(input())
    preorder = list(map(int,input().split()))
    inorder = list(map(int,input().split()))
    recursion(preorder, inorder)
    print()