트리 (4256번) - 백준 (BOJ)

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

4256번: 트리

 

 

백준 - 문제집 (1766번)

 

난이도 : Gold 2

알고리즘 : Recursive

풀이 소요 시간 : 45 mins

Time Complexity : O( N )

 

import sys
input = sys.stdin.readline
print = sys.stdout.write


def get_post(ps, pe, os, oe):
    if ps > pe:  return ''
    if ps == pe:  return f'{pre[ps]} '
    idx = ino[pre[ps]]
    return get_post(ps+1, ps+idx-os, os, idx-1) + get_post(ps+1+idx-os, pe, idx+1, oe) + f'{pre[ps]} '


if __name__ == '__main__':
    for _ in range(int(input())):
        n = int(input())
        pre = input().split()
        ino = {v: i for i, v in enumerate(input().split())}
        print(get_post(0, n-1, 0, n-1))
        print('\n')

 

트리 (Tree) 의 전위순회 (preorder) 와 중위순회 (inorder) 정보가 주어졌을 때,

후위순회 (postorder) 를 구하는 문제이다.

 

사실상 이 문제와 풀이 방법이 동일하다.

 

코드의 차이점이 있다면,

이 문제는 트리 복구 문제와 달리

리스트 슬라이싱 (list slicing) 이 아닌, index (인덱스) 로만 접근해서 해결했다.