백준_python 1991번 트리 순회 (Node class, 트리, 재귀)

<문제 링크>

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

 

 

<정답 코드>

 sol ) 재귀를 이용한 트리 탐색

import sys
input = sys.stdin.readline
 
class Node:
    def __init__(self, item, left, right):
        self.item = item
        self.left = left
        self.right = right
 
def pre_order(node):
    result.append(node.item)
    if node.left != '.':
        pre_order(tree[node.left])
    if node.right != '.':
        pre_order(tree[node.right])
 
def in_order(node):
    if node.left != '.':
        in_order(tree[node.left])
    result.append(node.item)
    if node.right != '.':
        in_order(tree[node.right])
 
def post_order(node):
    if node.left != '.':
        post_order(tree[node.left])
    if node.right != '.':
        post_order(tree[node.right])
    result.append(node.item)
 
# 입력 처리
n = int(input().strip())
tree = {}
for _ in range(n):
    i, l, r = input().strip().split()
    tree[i] = Node(i, l, r)
 
# 전위 순회
result = []
pre_order(tree['A'])
print(''.join(result))
 
# 중위 순회
result = []
in_order(tree['A'])
print(''.join(result))
 
# 후위 순회
result = []
post_order(tree['A'])
print(''.join(result))

 

line 4~8) 노드 클래스를 선언해 노드에 쉽게 접근할 수 있음

line 10~29) 재귀를 이용해 순회 구현하면 간단함

 

트리, 재귀 문제 더 풀어보면서 구현 연습을 해야겠다.