[백준] 1991 트리순회 python

www.acmicpc.net/problem/1991

1991번: 트리 순회

import sys; input = sys.stdin.readline
n = int(input())
ldic, rdic = dict(), dict()
for _ in range(n):
    p, ls, rs = input().split()
    ldic[p] = ls
    rdic[p] = rs

def pre(node='A'):
    global answer
    if node == '.':
        return
    answer += node
    pre(ldic[node])
    pre(rdic[node])

def ino(node='A'):
    global answer
    if node == '.':
        return
    ino(ldic[node])
    answer += node
    ino(rdic[node])

def pos(node='A'):
    global answer
    if node == '.':
        return
    pos(ldic[node])
    pos(rdic[node])
    answer += node
answer = ''
pre()
answer += '\n'
ino()
answer += '\n'
pos()
print(answer)

preorder, inorder, postorder에 대해 이해하면 쉽게 풀수있는 문제이다.

방문한 노드에 대해서 언제 처리할 것인지에 따라 전위, 중위, 후위 순회로 나뉜다.

전위순회는 현재노드, 왼쪽노드, 오른쪽노드 순으로 접근하면 되고,

중위순회는 왼쪽노드, 현재노드, 오른쪽노드 순으로 접근하면 되고,

후위순회는 왼쪽노드, 오른쪽노드, 현재노드 순으로 접근하면 된다.