[백준] 1991번 트리 순회 _ 문제 풀이



1. 문제

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

2. 풀이

python의 딕셔너리를 이용하여 문제를 해결합니다. 아래의 순서를 지키면서 문제를 해결합니다.

  • 전위순회 (Pre-order) : Root -> 왼쪽 subtree -> 오른쪽 subtree
  • 중위순회 (in-order) : 왼쪽 subtree -> Root -> 오른쪽 subtree
  • 후위순회 (post-order) : 왼쪽 subtree -> 오른쪽 subtree -> Root
n = int(input())
dic = {}
arr = []
for _ in range(n):
    m, l, r = input().split()
    dic[m] = {}
    if l != '.':
        dic[m]['l'] = l
    if r != '.':
        dic[m]['r'] = r

def preorder(m):
    arr.append(m)
    if dic[m].get('l'):
        preorder(dic[m]['l'])
    if dic[m].get('r'):
        preorder(dic[m]['r'])

def inorder(m):
    if dic[m].get('l'):
        inorder(dic[m]['l'])
    arr.append(m)
    if dic[m].get('r'):
        inorder(dic[m]['r'])

def postorder(m):
    if dic[m].get('l'):
        postorder(dic[m]['l'])
    if dic[m].get('r'):
        postorder(dic[m]['r'])
    arr.append(m)

preorder('A')
print(''.join(arr))
arr = []
inorder('A')
print(''.join(arr))
arr = []
postorder('A')
print(''.join(arr))