[백준/Python] 1991번 : 트리 순회

전위, 중위, 후위 순회를 재귀로 푸는 문제이다.

처음에 left, right 노드 저장 방식을 잘못 받아서 구현하는 데 애를 먹다가 옆자리 동료분한테 물어봤는데 정석 풀이가 있었다.

root 노드를 아스키 코드로 변경한 숫자를 인덱스로 하는 곳에 left, right 노드를 저장하는 방법이다.

해당 노드의 왼쪽 자식을 저장하는 l, 오른쪽 자식을 저장하는 r 리스트를 사용하면 재귀로 쉽게 풀 수 있다.

import sys

n = int(sys.stdin.readline())
l = [None]*26
r = [None]*26

for _ in range(n):
    node, left, right = map(str, sys.stdin.readline().split())
    if left != '.': l[ord(node)-ord('A')] = left
    if right != '.': r[ord(node)-ord('A')] = right

pre_ = []
in_ = []
post_ = []

def pre_order(root):
    if root is None: return
    pre_.append(root)
    pre_order(l[ord(root)-ord('A')])
    pre_order(r[ord(root)-ord('A')])

def in_order(root):
    if root is None: return
    in_order(l[ord(root)-ord('A')])
    in_.append(root)
    in_order(r[ord(root)-ord('A')])

def post_order(root):
    if root is None: return
    post_order(l[ord(root)-ord('A')])
    post_order(r[ord(root)-ord('A')])
    post_.append(root)

pre_order('A')
in_order('A')
post_order('A')

print(''.join(pre_))
print(''.join(in_))
print(''.join(post_))