알고리즘/백준
[백준] 2263번 트리의 순회 (파이썬)
알감자
2022. 1. 5. 23:25
2263번: 트리의 순회
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
www.acmicpc.net
코드
import sys
sys.setrecursionlimit(10**8)
n = int(input())
in_order = list(map(int, input().split(" ")))
post_order = list(map(int, input().split(" ")))
position = [0] * (n+1)
for i in range(n):
position[in_order[i]] = i
def pre_order(in_start, in_end, post_start, post_end):
if in_start > in_end or post_start > post_end:
return
root = post_order[post_end]
print(root, end=" ")
pre_order(in_start, position[root]-1, post_start, post_start+position[root]-in_start-1)
pre_order(position[root]+1, in_end, post_start+position[root]-in_start, post_end-1)
pre_order(0,n-1, 0,n-1)