이진 검색 트리
문제
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 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문제 풀이
🔓 문제 접근 과정
전위 트리는 가장 첫번째 요소가 루트 노드이다.
개수를 파악해서 layer가 몇개로 구성되어있는지 파악하려고 했다.
그런데 생각해보니 그럴 필요가 없었다.
이진 검색 트리이기 때문에 현재 요소와 이전 요소를 비교하면서 작으면 아래로 내려가면 된다.
이 문제는 하나의 기준점을 정해서 그 기준점보다 큰 수를 찾고 그 전까지 자르는 과정을 반복하면 된다.
즉 재귀이다.
한번 이 문제를 보면서 예를 들어보겠다.
이 문제에서 전위 순회의 결과를 리스트로 살펴보자면 이렇게 된다.
50 30 24 5 28 45 98 52 60
여기서 처음에는 50이 기준점이 된다.
그 후 다음요소를 차례로 50과 비교를 한다.
그리고 큰 수(98)가 나오면 그 수 전까지 자른다.
50 / 30 24 5 28 45 / 98 52 60
그리고 다시 30이 기준이 되고 다음을 순회하며 기준점인 30과 비교를 한다.
이런식으로 재귀를 통해서 비교를 계속 하면 잘려나가면서 후위순회의 순서로 출력이 된다.
def postorder(first, end):
if first > end:
return
mid = end + 1 # root보다 큰 값이 존재하지 않을 경우를 대비
for i in range(first+1, end+1):
if numList[first] < numList[i]:
mid = i
break
postorder(first+1, mid-1)
postorder(mid, end)
print(numList[first])
여기서 mid = end +1 을 한 이유 root보다 큰 값이 존재하지 않을 경우를 대비하기위해 있는것이다.
다음 예시를 봐보자
50 / 30 / 24 / 5 / 28 / 45 / 98 52 60
98이전의 요소는 다 비교가 되었고 이제 98부터 다음 요소와 비교하여 큰 값을 찾는다고 생각해보자.
여기서는 98보다 큰 수가 없다.
하지만 분류가 다 된것은 아니다.
이때 mid = end + 1 을 해주어 다음 요소로 넘어가게 해준다.
🔑 최종 코드
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10**6)
stdin = open('example.txt', 'r')
numList = []
while True:
try:
num = int(stdin.readline())
numList.append(num)
except:
break
def postorder(first, end):
if first > end:
return
mid = end + 1 # root보다 큰 값이 존재하지 않을 경우를 대비
for i in range(first+1, end+1):
if numList[first] < numList[i]:
mid = i
break
postorder(first+1, mid-1)
postorder(mid, end)
print(numList[first])
postorder(0, len(numList)-1)🧑🏻💻 이 문제를 풀면서 공부한 내용
deque
