백준 5639 이진 검색 트리 - 파이썬

문제.

 

풀이.

이진 트리는 루트 기준으로 왼쪽은 루트 값 보다 작은 수들, 오른쪽은 큰 수 이다.

즉 root값을 기준으로 왼쪽 인덱스, 오른쪽 인덱스를 찾아 값을 구하면 된다.

 

소스코드.

	import sys
	from collections import deque
	def order(start, end):
	if start > end:
	return
	root = tree[start]
	preorder.appendleft(root) # left, right, root 순이므로 appendleft를 이용한다.
	idx = start + 1
	while idx <= end:
	if tree[idx] > root:
	break
	idx += 1
	order(idx, end) #오른쪽 노드
	order(start+1, idx-1) # 왼쪽 노드
	sys.setrecursionlimit(10 ** 9)
	input = sys.stdin.readline
	preorder = deque()
	tree = []
	count = 0
	while count <= 10000:
	try:
	temp = int(input())
	except:
	break
	tree.append(temp)
	count += 1
	order(0, len(tree)-1)
	print(*preorder)

view raw 이진 검색 트리.py hosted with ❤ by GitHub