[Baekjoon 5639 / python / 골드5] 이진 검색 트리

import sys

sys.setrecursionlimit(10**9)  # 재귀호출 최대 깊이를 늘려준다

pre = []  # 전위순회 순서 입력받기

while True:

    try:

        n = int(sys.stdin.readline())

        pre.append(n)

    except:

        break

def postOrder(nodeList):  # 전위순회 결과를 입력받는다 생각지 말고, 그냥 노드 리스트를 입력받는다 생각하면 이해가 편함

    if len(nodeList) == 0:  # 빈 리스트라면 return

        return

   

    left, right = [], []

    root = nodeList[0]  # root노드 기준으로 작은값, 큰값으로 나눈다

    for i in range(1, len(nodeList)): # root노드 다음값부터 반복문 진행

        if nodeList[i] > root:  # root보다 큰 값이 나온다면, 해당 값과 그 이후값은 모두 오른쪽 서브트리에 위치함

            left = nodeList[1:i]

            right = nodeList[i:]

            break  # 두 그룹으로 나누었다면 반복 종료

    else:  # 만약 두 그룹으로 나누지 못했다면( root보다 큰 값이 없었다면 )

        left = nodeList[1:]  # 전부 left로 보내기

   

    postOrder(left) # 왼쪽 그룹으로 여행을 보내기 ( 갔다 오면서 알아서 왼쪽값 출력함 )

    postOrder(right) # 오른쪽 그룹으로 여행을 보내기 ( 갔다 오면서 알아서 오른쪽값 출력함)

    print(root) # 왼, 오 다 출력했으면 루트 노드 출력

postOrder(pre)

 

이진 검색 트리 문제다. 원래도 주석을 많이 다는 편인데 헷갈렸던 부분이 많아서 주석을 더욱 많이 달게 되었다.

 

어떤 이진 검색 트리의 전위순회 결과가 주어지고, 이를 토대로 해당 트리의 후위순회 결과를 출력하는 문제이다.

처음엔 전위순회 결과를 이용해 트리 인접행렬을 만든 후 후위 순회를 할까도 생각해 보고, 여러가지 생각을 해봤는데 잘 안되었다. 결국 다른 코드를 조금 참고해서 풀어냈다.

 

전위 순회 결과를 어떻게 막 바꿔서 답을 찾으려고 생각하는 것 보다는, 그냥 정렬되지 않은 노드 리스트를 입력받는다고 생각하고, 그것을 후위 순회로 돈다라고 생각하면 이해하기 한결 쉽다.

 

이진 검색 트리는 왼쪽 서브트리가 루트보다 작은 값, 오른쪽 서브트리가 루트보다 큰 값이기 때문에 이 조건을 기반으로 마치 트리를 만드는 것 같은 효과를 냈고, 이것을 후위 순회 방식으로 돌아서 해결할 수 있었다.