[python3] 백준 1991 (트리 순회, 트리, 재귀)

이번 문제는 순회 문제이다. 처음에는 트리를 어떻게 푸는지 몰라서 헤맸는데 어제 영상을 봤더니 쉽게 이해가 갔다.

https://www.youtube.com/watch?v=QN1rZYX6QaA 

 

정리하자면 

pre order = root, left, right 순서

in order = left, root, right 순서

post order = left, right, root 순서

따라서 순서만 기억해도 나중에 쉽게 떠올릴 수 있다. 이걸 토대로 문제를 풀면 아래와 같다.

adj = {}
N = int(input())

for i in range(N):
    A, B, C = input().split()
    if A not in adj:
        adj[A] = [B, C]

# 전위 순회 [root, left, right]
def recur(node, order):
    if node == '.':
        return
    left, right = adj[node]
    if order == 1:
        print(node, end="")
    recur(left, order)
    if order == 2:
        print(node, end="")
    recur(right, order)
    if order == 3:
        print(node, end="")

recur('A', 1)
print()
recur('A', 2)
print()
recur('A', 3)
print()