이진 검색 트리

문제

풀이

처음에 이진 검색 트리를 만들고 해당 트리에서 후위 순회하는 코드를 작성하였다.
하지만 시간초과가 발생하였다.

다른 블로그를 참고하였는데 전위 순회를 가지고 후위 순회를 나타낼 수 있다는 것이다.

전위 순회 특성상 루트, 왼쪽 서브트리, 오른쪽 서브트리 순으로 출력이 된다는 것이다.

루트 기준으로 작은 부분은 왼쪽 서브트리
루트 기준으로 큰 부분은 오른쪽 서브트리 가 된다.

재귀구조로 이러한 과정을 반복하면

왼쪽 서브 트리 오른쪽 서브트리 루트를 출력하게 하면 원하는 후위 순회를 나타낼 수 있게 된다.

for test_case in range(1):

    node = []

    while True:
        try:
            n = int(sys.stdin.readline().rstrip())
            node.append(n)
        except:
            break


    def postOrder(start, end):
        if start >= end:
            return

        mid = end

        for i in range(start + 1, end):
            if node[start] < node[i]:
                mid = i
                break

        postOrder(start + 1, mid)
        postOrder(mid, end)
        print(node[start])


    postOrder(0, len(node))

mid = end로 mid 초기값을 end로 주었는데
이것은 만약 왼쪽 서브트리만 있을 경우를 나타내주기 위해서이다.
이렇게 함으로서 시간초과 없이 통과할 수 있었다.