5639 이진검색트리

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6)


preorder = []

while True :
    try :
        preorder.append(int(sys.stdin.readline()))
    except :
        break


def postorder(start,end):
    if start >= end :
        return
    root = preorder[start]
    div = end
    # 현재 노드에서 갈리는 지점 찾기.
    for i in range(start+1,end):
        if root < preorder[i] :
            # 현재 노드보다 큰것이 있다면 여기가 분기점
            div = i
            break
    # 여기서 좌 우로 DFS를 진행
    # 순서는 후위순회이므로 왼->오->루트 이다.
    # 따라서 루트의 출력을 제일 마지막에 해주면됨
    postorder(start+1,div)
    postorder(div,end)
    print(root)

postorder(0,len(preorder))

3. 풀이 및 생각

문제 풀이

이 문제는 전위순회방식으로 데이터를 읽으면서 후위순회방식으로 데이터를 처리해야했다. 단, 전위 순회를 진행하면서 왼쪽 자식 노드는 부모 노드보다 항상 값이 작고, 오른쪽 자식 노드는 항상 값이 커야함을 유지해야했기때문에, 이 정보를 이용해서 전위순회방식을 고려해 좌우를 가를 수 있게 해주었다. 이렇게 가른 후에 후위순회방식을 통해서 단순하게 처리된 데이터를 출력만 해주면 된다. 전위순회가 루트->왼->오 순이면 후위순회는 왼->오->루트 순이므로 단순히 print의 위치만 잘 바꿔주면 된다.

나의 생각

이 문제는 내 힘으로 풀지 못했다. 그 이유는, 아직 전위,중위,후위에 대한 개념이 딱 잡혀있지 않아서.. 그래도 이번 문제를 풀면서 조금 더 개념을 다질 수 있게 되었다.