[백준] #1991 트리 순회(python)

📌문제

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

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

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

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력

ABDCEFG
DBAECFG
DBEGFCA

백준 1991번 문제

💡Idea

🎄트리가 부모 하나, 그 부모에 딸린 자식으로만 이루어진 작은 트리라고 생각하고 함수를 하나 만들어 재귀 방식으로 트리를 순회해나가면 됩니다.

동일하게 한 번만 순회하되, 각 순회 방식에 따라서 각각 다른 위치에서 노드를 출력할 수 있도록 하면 됩니다.

• 전위 순회의 경우, 루트 먼저 출력되어야 하므로 왼쪽과 오른쪽의 자식들을 순회하기 전에 노드를 출력할 수 있도록 합니다.
• 중위 순회의 경우, 왼쪽 자식이 먼저 출력되어야 하므로 왼쪽 자식을 순회하고 노드를 출력할 수 있도록 합니다.
• 후위 순위의 경우, 오른쪽 자식이 먼저 출력되어야 하므로 오른쪽 자식을 순회하고 노드를 출력할 수 있도록 합니다.

💻코드

• ⏰ 시간 : 68 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline
N = int(input())
tree = {chr(i + 65): [] for i in range(26)} # 부모:[왼쪽 자식, 오른쪽 자식] 딕셔너리
for _ in range(N):
    p, l, r = input().strip().split() # p 부모의 왼쪽 자식 l과 오른쪽 자식 r
    tree[p] = [l, r] # tree 딕셔너리 update 
preorder = [] # 전위 순회 순서를 담을 리스트
inorder = [] # 중위 순회 순서를 담을 리스트
postorder = [] # 후위 순회 순서를 담을 리스트


def traversal(tree, root):
    if root == '.': # 만약 root가 .이라면 아무것도 하지 않고 종료
        return
    preorder.append(root) # 전위 순회 리스트에 루트 추가
    traversal(tree, tree.get(root)[0]) # 왼쪽 자식 순회
    inorder.append(root) # 중위 순회 리스트에 루트 추가
    traversal(tree, tree.get(root)[1]) # 오른쪽 자식 순회
    postorder.append(root) # 후위 순회 리스트에 루트 추가


traversal(tree, 'A') # 루트인 A를 시작으로 트리 순회
print('%s\n%s\n%s' % (''.join(preorder), ''.join(inorder), ''.join(postorder)))