[Python] 백준 - 5639 이진 검색 트리

 

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

 

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

 

문제해결방법 - (구글링 참조)

 

1. 전위순회 결과를 활용해 후위순회를 출력하는 문제다.

 

 

출력 혹은 탐색 순서

전위순회 -> 50 30 24 5 28 45 98 52 60

후위순회 -> 5 28 24 45 30 60 52 98 50

 

이 순서에서 패턴을 찾아본다.

 

전위순회\인덱스	0	1	2	3	4	5	6	7	8
원소	50	(30	24	5	28	45)	(98	52	60)

 

후위순회\인덱스	0	1	2	3	4	5	6	7	8
원소	(5	28	24	45	30)	(60	52	98)	50

 

후위 순회 방법은 (왼쪽)(오른쪽)(루트노드) 의 순서로 탐색 및 출력한다.

전위 순회에서 root노드보다 큰 경우를 기점으로 분할하여, 후위순회 방법을 출력되도록 하면 된다는 것을 알 수 있다.

 

mid 를 r+1로 하여 mid가 가장 클 경우, 오른쪽자식을 탐색하는 재귀함수가 생략되고 

왼쪽 탐색 재귀함수가 l+1, r로 맞아떨어지게 짜여지는 것이 절묘한 것 같다.

 

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

d = []
while True:
	try:
		n = int(input())
		d.append(n)
	except:
		break

def POST(l, r):
	if l > r:
		return
	root = d[l]
	mid = r+1
	for i in range(l+1, r+1):
		if d[i] > root:
			mid = i
			break
	POST(l+1, mid-1)
	POST(mid, r)
	print(root)

POST(0, len(d)-1)

'''
def END(i):
	if i == '.':
		return
	END(graph[i][0])
	END(graph[i][1])
	print(i, end='')
'''