[백준/파이썬] 5639번 이진 검색 트리 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 5639번 이진 검색 트리
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

전위 순회 결과가 주어졌을 때, 후위 순회 결과를 출력하는 문제입니다.

코드

import sys

sys.setrecursionlimit(10000)

class Node:
    def __init__(self, key, left = None, right = None):
        self.key = key
        self.left = left
        self.right = right

def post_order_traversal(tree, results):
    if tree.left != None: post_order_traversal(tree.left, results)
    if tree.right != None: post_order_traversal(tree.right, results)
    results.append(tree.key)

for line in sys.stdin:
    key = int(line)
    try:
        tmp = tree
        while True:
            if key < tmp.key:
                if tmp.left is None:
                    tmp.left = Node(key)
                    break
                tmp = tmp.left
            elif key > tmp.key:
                if tmp.right is None:
                    tmp.right = Node(key)
                    break
                tmp = tmp.right
    except: tree = Node(key)

results = []
post_order_traversal(tree, results)
print('\n'.join(map(str, results)))

설명

전위 입력 순서대로 BST를 구성한 뒤, 재귀 후위 순회(왼쪽-오른쪽-루트)로 결과를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---