이진 검색 트리

solved_ac[Class4][이진 검색 트리](https://www.acmicpc.net/problem/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

예제 출력 1

5
28
24
45
30
60
52
98
50

문제 해석

이진 트리의 전위 순회로 입력을 받아서 후위 순회로 출력을 하는 것이다. 입력을 list에 차례대로 입력을 받고 해당 list[i + 1]이 list[i]보다 크다면 오른쪽 자식 노드, 그게 아니라면 왼쪽 자식 노드로 설정을 해주면서 풀어야한다. 전위 순회는 재귀 함수의 호출 순서와 같다.

풀이

• 먼저 base case에 대해서 생각을 해봐야한다. 전위 순회는 재귀 함수의 호출 순서와 같으니 무조건 재귀로 푸는것이 이상적이다라고 생각을 했다.
• list에 전위 순회 순서로 입력값들을 받는다.
• list의 0번지부터 시작을 해서 오른쪽 노드와 왼쪽 노드로 나눈다.
• 오른쪽 노드는 기준 노드보다 크면 오른쪽이기 때문에 루프를 돌면서 list안에서 오른쪽 노드의 index 값을 추출해낸다.
• 오른쪽 노드가 없을 수도 있으니 오른쪽 노드를 저장해주는 변수를 루프를 돌기전에 end + 1 값으로 해준다.
• 그래야 루프를 돌아서 right_node 값을 업데이트 못해주더라도 문제가 안생긴다.
• 그리고 전위 순회는 왼쪽 노드부터 밑에서 훑고 올라오기 때문에 이미 검사한 start index보다 1 증가시킨 start + 1 부터 right_node - 1까지 범위로 호출해준다.
• 그리고 오른쪽 노드는 right_node부터 end까지 범위로 호출해준다.

base case

root node : list[start]

left node : 함수(start + 1, right_node - 1)

right node : 함수(right_node, end)

print(root node)

전체 골격

전위순회는 재귀함수의 호출 순서와 같다.

예시 문제를 보자.

1.
start = 0
end = len(list) - 1
root = list[start] = 50
루프
right_node_index = 6 = 98의 index
함수(start = start + 1, end = right_node_index - 1)
	2. 
	start = 1
	end = 5
	root = list[start] = 30
	루프
	right_node_index = 5 = 45의 index
	함수(start = start + 1, end = right_node_index - 1)
		3. 
		start = 2
		end = 4
		root = list[start] = 24
		루프
		right_node_index = 4 = 28의 index
		함수(start = start + 1, end = right_node_index - 1)
			4. 
			start = 3
			end = 3
			root = list[start] = 5
			start와 end가 같아서 루프를 돌지 못함. 
            그래서 right_node_index가 업데이트 되지 않음.
			그렇기 때문에 루프를 돌기 전에 
            right-node_index를 end + 1로 업데이트를 시켜주는것.
			왜 굳이 end + 1이냐면 계속 함수를 호출하면서 end 범위를 r
            right_node_index에서 1개씩 줄여줌.
			그러면 start는 1개씩 늘어나는데 end 범위는 계속 그 자리에서 기다림.
			그러다가 start값이 end값을 역전하는 순간 재귀를 return해주면 됨.
			start가 end를 역전하는 경우는 더이상 작은 노드가 없을 때 일어남.
			함수(start = start + 1, end = right_node_index - 1)
				5. 
				start = 4
				end = 3
				start가 end 역전. 더이상 작은 노드가 없다는 뜻.
			함수(right_node_index, end)
				6.
				start = 4
				end = 3
				return
				5번과 6번은 뭘 의미하냐면 가장 작은 노드 5가 추려졌고 
                5의 자식노드 왼쪽, 오른쪽 둘다 없다는 뜻
		함수(right_node_index, end)
			7. 
			start = 4
			end = 4
			root = list[start] = 28
			루프돌지 않고(start와 end가 같기 때문) 
            그 전에 right_node_index = end + 1 = 5로 됨.
			함수(start = start + 1, end = right_node_index - 1)
				8. 
				start = 5
				end = 4
				return
			함수(right_node_index, end)
				9.
				start = 5
				end = 4
				reuturn
	함수(right_node_index, end)
		10.
		start = 5
		end = 5
		root = list[start] = 45
		루프돌지 않음
		right_node_index = end + 1 = 6
		함수(start = start + 1, end = right_node_index - 1)
			11.
			start = 6
			end = 5
			return
		함수(right_node_index, end)
			12.
			start = 6
			end = 5
			return
함수(right_node_index, end)
	13.
	start = 6
	end = 8
	root = list[start] = 98
	루프
	right_node_index = 98보다 큰 수가 없기 때문에 그 전에 end + 1로 잡아놓은 값 = 9
	함수(start = start + 1, end = right_node_index - 1)
		14.
		start = 7
		end = 8
		root = list[start] = 52
		루프
		right_node_index = 60의 index 값 = 8
		함수(start = start + 1, end = right_node_index - 1)
			15.
 			start = 8
			end = 7
			return
		함수(right_node_index, end)
			16. 
			start = 8
			end = 8
			root = list[start] = 60
			루프 안돔
			right_node_index = 9
			함수(start = start + 1, end = right_node_index - 1)
				17.
				start = 9
				end = 8
				return
			함수(right_node_index, end)
				18.
				start = 9
				end = 8
				return
	함수(right_node_index, end)
		19.
		start = 9
		end = 8
		return

import sys

sys.setrecursionlimit(10**9)

list = []

while True:
    try:
        n = sys.stdin.readline()
        list.append(int(n))
    except:
        break


def binary(start, end):
    if start > end:
        return
    right_node = end + 1
    root = list[start]
    for i in range(start + 1, end + 1):
        if list[i] > root:
            right_node = i
            break
    binary(start + 1, right_node - 1)
    binary(right_node , end)
    print(root)
        
    
    
binary(0, len(list) - 1)

고찰

tree에 대해서 잘 모르는 상태로 접근을 해서 많이 힘들었다. 디버깅도 많이 해보고 최대한 답지를 보지 말자는 식으로 풀다가 총 5시간이 걸렸다... 그래도 이진 탐색 트리에 대해서 전위 순회, 중위 순회, 후위 순회를 알게 되어서 다행이라고 생각한다.