[파이썬/백준 1991]트리 순회

문제

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

 

코드

import sys

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(node):
    if node is None:
        return
    print(node.val, end='')
    if node.left:
        preorder(tree[node.left])
    if node.right:
        preorder(tree[node.right])

def inorder(node):
    if node is None:
        return
    if node.left:
        inorder(tree[node.left])
    print(node.val, end='')
    if node.right:
        inorder(tree[node.right])

def postorder(node):
    if node is None:
        return
    if node.left:
        postorder(tree[node.left])
    if node.right:
        postorder(tree[node.right])
    print(node.val, end='')


input = sys.stdin.readline
n = int(input())
tree = dict()
for _ in range(n):
    val, left, right = input().split()
    if left == '.':
        left = None
    if right == '.':
        right = None
    tree[val] = Node(val, left, right)

preorder(tree['A'])
print()
inorder(tree['A'])
print()
postorder(tree['A'])

 

그동안 리트코드에서 트리 문제를 풀 때는 트리에 노드가 이미 다 들어가있는 상태여서 그냥 순회 알고리즘만 작성하면 됐는데, 이번에는 트리에 데이터도 직접 넣어야해서 도대체 어떻게 구현할지 한참 고민했다. 물론 해결책은 언제나 간단했고... 이번에는 딕셔너리를 쓰니까 바로 해결됐다. 

 

 

링크

www.acmicpc.net/problem/1991

1991번: 트리 순회