[BOJ]1991 - 트리 (Python)

문제 

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

코드 

import sys
input = lambda : sys.stdin.readline().strip()


def preorder(root):
    if root == '.':
        return
    print(root, end="")
    preorder(tree[root][0])
    preorder(tree[root][1])


def inorder(root):
    if root == '.':
        return
    inorder(tree[root][0])
    print(root, end="")
    inorder(tree[root][1])


def postorder(root):
    if root == '.':
        return
    postorder(tree[root][0])
    postorder(tree[root][1])
    print(root, end="")


n = int(input())
tree = {}
for i in range(n):
    root, left, right = input().split()
    tree[root] = [left, right]

preorder('A')
print()
inorder('A')
print()
postorder('A')

 

풀이 

트리 순회를 까먹어서 다시 공부하고 문제를 풀었다 

전위 순회(preorder) : root → left → right

중위 순회(inorder) : left → root → right

후위 순회(postorder) : left → right → root 

 

위와 같이 순회하게 되는데, 하나의 노드와 그의 왼쪽 자손과 오른쪽 자손을 다 저장하기 위해서 사전(dictionary)을 사용했다

node가 key가 되고, 그에 해당하는 left, right가 value로 들어가게 된다 

 

preorder는 node를 먼저 출력한 뒤에, 그 node의 left와 right를 차례대로 순회한다 (재귀) 

inorder는 node의 left를 순회하고, node를 출력하고, 그의 right를 순회한다 

postorder는 node의 left, right를 차례대로 순회한 뒤에 node를 출력하면서 끝낸다 

 

기본적인 문제지만 개념을 까먹어서 도움을 받아 풀 수 있었다