백준 1991 파이썬 - 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

코드

import sys
n = int(sys.stdin.readline())
node = {}
for _ in range(n):
    root, left, right = sys.stdin.readline().rstrip().split()
    node[root] = [left, right]
def pre(root):
    if root != '.':
        print(root, end='')
        pre(node[root][0])
        pre(node[root][1])
def inner(root):
    if root != '.':
        inner(node[root][0])
        print(root, end='')
        inner(node[root][1])
def post(root):
    if root != '.':
        post(node[root][0])
        post(node[root][1])
        print(root, end='')
pre('A')
print()
inner('A')
print()
post('A')

풀이

트리를 함수를 통해 문제에서 주어진 순서대로 탐색하고 출력하면된다. 첫 노드는 무조건 A인 것을 활용한다.