백준 4256번 파이썬

문제

https://www.acmicpc.net/problem/4256

4256번: 트리

풀이

1. 전위 순위의 첫 번째 원소를 기준으로 중위 순위를 나눈다.

2. 전위 순위의 첫 번째 원소를 제거한다.

3. 중위 순위의 원소가 없을 때까지 1과 2의 과정을 반복한다

예를 들어 전위 순위 : 3 6 5 4 8 7 1 2 / 중위 순위 : 5 6 8 4 3 1 2 7 라고 한다면, 트리는 다음 과정으로 만들어진다.

매번 확정된 숫자(매번 전위 순위의 첫 번째 원소)를 동그라미 쳐주었다.

코드

def find_post_order(pre_order: list, in_order: list):
    if not in_order:
        return

    p = pre_order.pop(0)
    idx = in_order.index(p)

    find_post_order(pre_order, in_order[:idx])
    find_post_order(pre_order, in_order[idx + 1:])
    print(p, end=" ")


for _ in range(int(input())):
    n = int(input())
    pre_order = list(map(int, input().split()))
    in_order = list(map(int, input().split()))
    find_post_order(pre_order=pre_order, in_order=in_order)
    print()