백준 1991 트리 순회

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

 

 이 문제는 A가 뿌리로 시작하는 트리를 전위,중위,후위 순회한 결과를 출력하는 문제이다. 

 

 전위순회는 루트,왼쪽서브트리,오른쪽서브트리 순으로 순회하는 것이고 중위순회는 왼쪽서브트리,루트,오른쪽서브트리 순으로 순회하는 것이고, 후위순회는 왼쪽서브트리,오른쪽서브트리,루트 순으로 순회하는 것이다. 

 

 이 문제는 필자는 먼저 딕셔너리를 이용하여, 트리를 구현하고, 재귀를 이용하여 왼쪽,오른쪽 서브트리를 계속해서 호출하여 잎에 닿을 때까지 깊숙이 내려가 잎에서 재귀를 멈추고 리턴하는 식으로 풀었다. 이 때 간단하게 순서만 조금 바꿔주면 전위,중위,후위를 각각 구현할 수 있다.

 

import sys
input = sys.stdin.readline

def pre_find(p):#전위
    if tree[p][0] == '.' and tree[p][1]=='.':
        return p
    elif tree[p][0] == '.':
        return p+pre_find(tree[p][1])
    elif tree[p][1] == '.':
        return p+pre_find(tree[p][0])
    else:
        return p+pre_find(tree[p][0])+pre_find(tree[p][1])

def inorder_find(p):#중위
    if tree[p][0] == '.' and tree[p][1]=='.':
        return p
    elif tree[p][0] == '.':
        return p+inorder_find(tree[p][1])
    elif tree[p][1] == '.':
        return inorder_find(tree[p][0])+p
    else:
        return inorder_find(tree[p][0])+p+inorder_find(tree[p][1])

def post_find(p):#후위
    if tree[p][0] == '.' and tree[p][1]=='.':
        return p
    elif tree[p][0] == '.':
        return post_find(tree[p][1])+p
    elif tree[p][1] == '.':
        return post_find(tree[p][0])+p
    else:
        return post_find(tree[p][0])+post_find(tree[p][1])+p

tree = dict()

for _ in range(int(input().rstrip())):
    p,l,r = input().rstrip().split()
    tree[p] = [l,r]


print(pre_find('A'))
print(inorder_find('A'))
print(post_find('A'))