[알고리즘] 백준 1991번 : 트리 순회 (파이썬)

백준 1991번 : 트리 순회
난이도 : 실버 1

- 문제 소개

- 조건

• 없음

- 코드

import sys

N = int(sys.stdin.readline().strip())
tree = {}

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

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

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

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

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

- 해설

재귀를 이용해서 이진 트리를 만들고, 전위 순회, 중위 순회, 후위 순회를 출력해보는 문제입니다. tree라는 딕셔너리를 만들어주고, root, left, right를 입력받습니다. 받음과 동시에 tree[root] = [left, right]로 저장을 해줍니다. 이러면 tree['A'] = ['B', 'C']가 되고, tree['B'] = ['D']가 되는데, 재귀로 접근할 수 있게 됩니다. 전위 순회(preorder)는 루트값을 출력한 뒤 left와 right값 출력, 중위 순회(inorder)는 left값 출력, 루트값 출력, right값 출력, 후위 순회(postorder)는 left값과 right값을 출력하고 루트값을 출력해줍니다. 이런 함수들을 만들어주고, 루트값 'A'를 매개변수로 입력해서 결과를 얻어낼 수 있었습니다.