백준 1991번: 트리 순회 [pyhon]

난이도 : 실버 1
유형 : 트리
https://www.acmicpc.net/problem/1991

문제

트리를 입력받고,

• 전위 순회 (Pre-order)
• 중위 순회 (In-order)
• 후위 순회 (Post-order)

한 결과를 각각 출력하는 문제이다.

전위: 루트 → 왼쪽 → 오른쪽
중위: 왼쪽 → 루트 → 오른쪽
후위: 왼쪽 → 오른쪽 → 루트

전,중,후는 루트의 위치를 의미한다고 생각하면 편하다.

아이디어

• 트리 구조를 딕셔너리로 저장
  tree = { 부모노드: [왼쪽자식, 오른쪽자식] } 형태로 구성
  예제 1을 트리로 입력받았을 때 구조
  

• 각 노드를 루트로 재귀적으로 순회
• 세 가지 순회를 각각 재귀함수로 구현

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input()) # 노드의 개수
tree = {} #  `tree = { 부모노드: [왼쪽자식, 오른쪽자식] }` 형태로 구성

for _ in range(N):
    root, left, right = input().strip().split()
    tree[root] = [left,right]

def preorder(node):
    if node == ".":
        return
    print(node, end="") # 루트
    preorder(tree[node][0]) # 왼쪽
    preorder(tree[node][1]) # 오른쪽

def inorder(node):
    if node ==".":
        return
    inorder(tree[node][0]) # 왼
    print(node, end="") # 루트
    inorder(tree[node][1]) # 오른쪽

def postorder(node):
    if node ==".":
        return
    postorder(tree[node][0]) # 왼
    postorder(tree[node][1]) # 오른쪽
    print(node, end="") # 루트

preorder("A")
print()
inorder("A")
print()
postorder("A")