(Python/🥇5)백준알고리즘 5639번: 이진 검색 트리

 

문제 바로가기

백준 알고리즘 5639번

문제:

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

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

 

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

입력:

 

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

출력:

 

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

 

풀이:

재귀 무엇을 하는지 생각하지 말고, 그냥 넘겨준다 생각한다.

가게에 가서 2명에서 먹으려고 할때 저기 창가에 있는 4인석 테이블에 내가 걸어가서 앉겠습니다. 가 아니라 2인 자리 주세요. 라는 식으로

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)


pre = []
while True:
    try:
        pre.append(int(input()))
    except:
        break
def dfs(start,end):
    if start > end:
        return
    mid = end + 1 ## 맨 오른쪽 가는게 없을 수 도 있음
    for i in range(start+1, end+1):
        if pre[start] < pre[i]:
            mid = i
            # print(start,pre[start],"ahah",i,pre[i], mid)
            break
    dfs(start+1,mid-1)
    dfs(mid,end)
    print(pre[start])

dfs(0, len(pre)-1)

mid  = end +1 는 루트 노드보다 큰 노드가 없을수도 있기 때문이다. 전부 노드를 왼쪽 서브트리로 만들기 위해서.

for 문을 돌리다가 큰 값이 나오면 그 뒤로는 오른쪽 트리니깐 mid를 바꿔주고 break

 

 

dfs(start+1,mid-1) # 왼쪽 트리 탐색
dfs(mid,end) # 오른쪽 트리 탐색
print(pre[start]) #루트 노드 출력