[백준] 1991_트리 순회 (Python)

1991_트리 순회 (Python)

0. 출처

• 유형 : 트리 (silver 2)
• 링크 : 1991번: 트리 순회

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 각 노드, 왼쪽 노드, 오른쪽 노드가 주어졌을 때
>> 어떻게 tree 에 저장할 것인지?
>> set() 형태로 저장해보자.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

- 예제 출력 1 -
ABDCEFG
DBAECFG
DBEGFCA

(3) 코드

n = int(input())

tree = {}

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

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

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

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

preorder('A')
print()        # 줄바꿈 용도
inorder('A')
print()        # 줄바꿈 용도
postorder('A')

(4) 정리

재귀를 잘 이해해야 이해할 수 있는 풀이이다.

전위 순회, 중위 순회, 후위 순회 개념이 코드에 그대로 적용된 풀이이다.

(5) 참고

참고 풀이