[백준] 2263 트리 순회

---

중위 순회와 후위 순회가 주어지고 전위 순회를 구하는 문제이다.

알고리즘 자체는 어렵지 않지만 메모리와 시간 초과로 인해 최적화가 조금 필요 했다.

참고: https://white-board.tistory.com/129

 

최적화가 필요한 부분은 후위 순회 결과에서 선택한 원소를 중위 순회 결과에서 인덱스를 구하는 부분인데, 이는 파이썬의 딕셔너리를 사용해서 O(1) 시간에 찾을 수 있도록 헀다.

 

 

Python

	from sys import stdin, setrecursionlimit
	readline = stdin.readline
	setrecursionlimit(10 ** 6)
	N = int(readline())
	inorder = list(map(int, readline().split()))
	postorder = list(map(int, readline().split()))
	p_idx = len(postorder) - 1
	def solve():
	index = dict()
	stack = []
	for i, n in enumerate(inorder):
	index[n] = i
	dfs(0, N-1, index, stack)
	stack.reverse()
	print(*stack)
	def dfs(in_s, in_e, index, stack):
	global p_idx
	if in_s > in_e:
	return
	root = postorder[p_idx]
	p_idx -= 1
	dfs(index[root]+1, in_e, index, stack) # 오른쪽 서브 트리
	dfs(in_s, index[root]-1, index, stack) # 왼쪽 서브트리
	stack.append(root)
	solve()

view raw BOJ2263.py hosted with ❤ by GitHub