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

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다. 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오. 입력 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다. 출력 입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

예시로 주어진 이진트리

전회순위를 후위순회로 바꿔 출력하는 문제이다.

주어진 예시

50
30
24
5
28
45
98
52
60

를 입력 받았다고 했을때 배열 형태로 트리를 만들면 아래와 같은 구조를 띄운다

이렇게 주어진 배열을 트리 구조로 만들었다면 이제 후위순회로 바꿀 차례

후위순회는 (왼쪽-오른쪽-루트) 특징을 띄우고 있다. 즉 젤 처음엔 왼쪽으로 가면서 자식노드가 없는 노드부터 검색을 시작하면 된다 그거 다 마치면 오른쪽도 ㄱㄱ

 

그림으로 나타내면 아래와 같은 순서로 출력을 해야한다.

1. 재귀 함수를 통해서 선택된 노드가 자식이 없다는걸 판단해야한다.

2. 자식이 있다면 우선 왼쪽을 우선으로 탐색을 하여 자식이 없는 노드까지 재귀함수로 호출한다.3. 왼쪽 오른쪽 모든 자식이 없다면 print를 통해 해당 노드를 출력한다.4. 출력된 후 재귀로 호출된 함수를 return받아 오른쪽도 노드가 있는지 확인한다.5. 오른쪽 자식이 없다면 출력 있다면 오른쪽 자식의 값으로 재귀를 재호출한다.6. 오른쪽 자식값에 딸린 자식이 없다면 해당 값을 출력하고 return한다.7. 다시 부모 노드로 돌아와 이번에야 말로 자식이 없을테니 print로 출력하고 부모 노드의 부모로 간다.

 

이 과정을 반복하면 성공! 해서 내 머릿속에 스케치대로 코드를 작성했지만 결과는 시간초과였다. 기본 재귀 깊이 제한때문에 그런듯 하다.

import sys
sys.setrecursionlimit(10**6)

#입력받을 원소 리스트
num_list=[]
while True:
    try:
        num=int(input())
        num_list.append(num)
    except:
        break

def postorder(left,right):
    #순서 역전시 종료
    if left>right:
        return
    else:
        mid=right+1        #분할 기준
        for i in range(left+1,right+1):
            #해당 원소가 현재 노드보다 크다면 그 전까지는 왼쪽 서브 트리,
            #해당 원소 이후는 오른쪽 서브 트리이다.
            if num_list[left]<num_list[i]:
                mid=i
                break
        postorder(left+1,mid-1)
        postorder(mid,right)
        print(num_list[left])

postorder(0,len(num_list)-1)

해서 인터넷의 코드를 참고했고

훨씬 깔끔한 코드를 확인할 수 있었다.

백준 예제로 설명을 해보면 (데이터 입력받는 부분은 생략)

1.  마지막 줄에 (0,8)로 파라메터값을 넘겨 함수를 실행시킨다.

2. num_list[0] -> 50 보다 크다면 모두 오른쪽 노드 이므로 그 전까지 계속 for문을 돌린다.

3. 50보다 큰 98을 만나면 스탑 mid값이 98의 위치를 저장한다 (left = 1, mid = 6, right=5)

4. 순서가 역전 되었는지 확인해보고 안됐다면 (left+1,mid-1)로 파라메터 값을 넘겨 함수를 실행한다.

5. 이 과정을 반복하여 부모 노드가 없는 3번 노드가 닿을때까지 즉, left>right를 만족할때까지 위 순서를 반복한다.