[baekjoon] 백준 1991번 : 트리 순회 (by python 파이썬) 재귀

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

1991번: 트리 순회

 

정답 code

#트리 순회
import sys
input = sys.stdin.readline

#전위 순회
def preorder(root):
    if root != '.':
        print(root, end='')
        preorder(tree[root][0])
        preorder(tree[root][1])

#중위 순회
def inorder(root):
    if root != '.':
        inorder(tree[root][0])
        print(root,end='')
        inorder(tree[root][1])

#후위 순회
def postorder(root):
    if root != '.':
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root, end='')

n = int(input())
tree = {}
for _ in range(n):
    m,l,r = input().strip().split()
    tree[m] = [l,r]


preorder("A")
print()
inorder("A")
print()
postorder("A")

 

solution

이번문제는 재귀 함수를 통해 풀었다.

트리는 딕셔너리로 표현하였다.

 

전위(preorder)순회 에는 부모노드를 출력하고 좌측 자식노드를 재귀한후 우측 자식노드를 재귀해주며 출력한다.

중위(inorder)순회에는 좌측 자식노드를 재귀한후 출력해나간후 부모노드를 그 후에 우측노드를 재귀해준다.

후위(postorder)순회에는 좌측 자식노드를 재귀후 우측자식노드를 재귀, 그 후로 부모노드를 출력해준다.

결국 언제출력하느냐에 차이다. 

 

후에 비슷한유형의 문제가 나오면 훨씬 빠르게 해결 할 수 있을 것 같다.