BOJ 4256번: 트리

www.acmicpc.net/problem/4256

4256번: 트리

아이디어:

이번에는 전위순회와 후외순회를 가지고 중위순회를 구하는 문제이다..

앞선 문제와 비슷하게 풀 수 있을 것 같다. 전위순회는 제일 첫번째 원소가 루트니까 루트를 일단 찾으면 중위순회를 오른쪽, 왼쪽 서브트리로 나눌 수 있다. 그리고 후위순회는 루트를 제일 마지막에 출력하니까 배열에 순서대로 저장한 후 반대로 출력하면 될 것 같다.

 

익숙해지면 이 유형 문제는 빠르게 풀 수 있을 것 같다!

#4256 트리
import sys
sys.setrecursionlimit(10**9)

def solve(instart, inend, prestart, preend):
    if (instart>inend or prestart>preend): return
    root = preorder[prestart]
    ans.append(root)

    div = index[root]
    right = inend - div

    solve(div+1, inend, preend-right+1, preend)
    solve(instart, div-1, prestart+1, preend-right)

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    preorder = list(map(int, sys.stdin.readline().split()))
    inorder = list(map(int, sys.stdin.readline().split()))

    index = [0]*(n+1)
    for i in range(n):
        index[inorder[i]] = i #root 위치 찾는 걸 빠르게 하기 위해서
    ans = []
    solve(0,n-1,0,n-1)
    for i in range(n-1, -1, -1):
        print(ans[i], end=" ")
    print()