백준(5639) - 이진 검색 트리 Python

백준(5639) - 이진 검색 트리

문제풀이: 이진트리, 파이썬

이진트리에서 전위 순회(preorder) 된 값을 후위 순회(postorder) 값으로 바꾸는 문제이다.

• 왼쪽 자식 노드는 루트보다 작고, 오른쪽 자식노드는 루트보다 크다는 것을 이용해서 자식노드가 없는 노드부터 찾아서 하나씩 출력해주면 된다.
• 그림으로 표현하려고 했으나 코드로 보는것이 오히려 더 직관적으로 이해가 잘 될 것 이다.

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def post(start, end):
    if start > end:
        return
    else:
        root = pre[start]
        div = end + 1 # for문을 돌지 못할경우 다음 post에서 바로 빠져나올수 있도록 초기화
        for pos in range(start+1, end+1):
            if root < pre[pos]:
                div = pos
                break
        post(start+1, div-1)
        post(div, end)
        print(root)

pre = []
while True:
    try:
        x = int(input())
        pre.append(x)
    except:
        break
post(0, len(pre)-1)