BaekJoon 1991번 : 트리 순회 (python)

BaekJoon 1991번 : 트리 순회 (S1 66.940%)

트리 순회 문제

이번 문제는 트리에서 순회할 수 있는 세가지 방법을 통해 주어진 트리의 순회 결과를 출력하는 문제이다.

• 기본적으로 파이썬에서 tree형태를 가장 쉽게 구현할 수 있는 방법은 dict자료형을 이용해 dict[root] = (left,right)형태로 트리를 저장할 수 있다.
• 순회의 방법 중 전위 순회는 (루트)(왼쪽)(오른쪽) 순으로 방문하게 되고 중위 순회(왼쪽)(루트)(오른쪽) 순으로 방문하게 되고 후위 순회는 (왼쪽)(오른쪽)(루트) 순으로 방문하게 된다. 이때의 방문 함수를 재귀함수를 통해 쉽게 구현할 수 있다.

import sys
input = sys.stdin.readline

def pre_order(node) :
    print(node, end='')
    if tree[node][0] != '.' :
        pre_order(tree[node][0])
    if len(tree[node]) <2 or tree[node][1] != '.' :
        pre_order(tree[node][1])

def in_order(node) :
    if tree[node][0] != '.' :
        in_order(tree[node][0])
    print(node, end='')
    if len(tree[node]) <2 or tree[node][1] != '.' :
        in_order(tree[node][1])

def post_order(node) :
    if tree[node][0] != '.' :
        post_order(tree[node][0])
    if len(tree[node]) <2 or tree[node][1] != '.' :
        post_order(tree[node][1])
    print(node, end='')

n = int(input())
tree = {}

for _ in range(n) :
    s = list(map(str,input().split()))
    tree[s[0]] = (s[1],s[2])
pre_order('A')
print()
in_order('A')
print()
post_order('A')

개선된 코드

import sys
input = sys.stdin.readline

n = int(input())
node = dict()

for _ in range(n) :
    root, left, right = map(str,input().split())
    node[root] = (left,right)

pre_ = ''
in_ = ''
post_ = ''

def ex(data) :
    global pre_, in_, post_
    
    pre_ += data
    if node[data][0] != '.' :
        ex(node[data][0])

    in_ += data
    if node[data][1] != '.' :
        ex(node[data][1])

    post_ += data

ex('A')
print(pre_)
print(in_)
print(post_)