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

💡문제

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

💡풀이

참 재귀스러웠던 문제.

재귀함수를 이해하고 있다면 풀 수 있다.
문제에도 친절히 힌트가 적혀있다.

전위 순회 // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회 // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회 // (왼쪽 자식) (오른쪽 자식) (루트)

보자마자, 마치 하노이의 탑처럼 재귀를 쓰고 싶은 욕구가 물씬 생긴다.
따라서, input을 Tree 자료구조에 맞게끔 입력해주고, 위처럼 재귀함수를 작성해주면 문제를 해결할 수 있겠다.
과정은 다양해질 수 있으나, 필자의 경우 dictionary 자료형으로 input을 받았으니 참고하자.

💡코드

import sys

def order(root, tree, type):
    if root == ".":
        return ""
    leftLeaf, rightLeaf = tree[root]
    if type < 0:
        return root + order(leftLeaf, tree, type) + order(rightLeaf,tree, type)
    elif not type:
        return order(leftLeaf, tree, type) + root + order(rightLeaf, tree, type)
    else:
        return order(leftLeaf, tree, type) + order(rightLeaf, tree, type) + root

def main():
    I = sys.stdin.readline
    tree = {}
    root = 'A'
    for _ in range(int(I())):
        a, *b = I().split()
        tree[a] = b
    for type in range(-1, 2):
        print(order(root, tree, type))

if __name__ == "__main__":
    main()