[백준] 1991번(트리 순회)

백준 1991번

최종 제출 코드

from collections import deque

queue = deque()

ele_dict = dict()
ind_dict = dict()
ind_dict['A'] = 0
ele_dict[0] = 'A'
n = int(input())

for i in range(n):
  parent, left, right = input().split()

  left_index = ind_dict[parent]*2+1
  right_index = ind_dict[parent]*2+2
  
  if left != '.':
    ele_dict[left_index] = left
    ind_dict[left] = ind_dict[parent]*2+1
  if right != '.':
    ele_dict[right_index] = right
    ind_dict[right] = ind_dict[parent]*2+2

pre_result = []
in_result = []
post_result = []

def preorder(index):

  left = index*2+1
  right = index*2+2

  pre_result.append(ele_dict[index])
  if left in ele_dict: preorder(left)
  if right in ele_dict: preorder(right)

def inorder(index):

  left = index*2+1
  right = index*2+2
  
  if left in ele_dict: inorder(left)
  in_result.append(ele_dict[index])
  if right in ele_dict: inorder(right)

def postorder(index):

  left = index*2+1
  right = index*2+2
  
  if left in ele_dict: postorder(left)
  if right in ele_dict: postorder(right)
  post_result.append(ele_dict[index])

preorder(0)
inorder(0)
postorder(0)

print(''.join(pre_result))
print(''.join(in_result))
print(''.join(post_result))

◼ 재귀함수를 통해서 트리순회

• 재귀함수를 호출하고, 현재의 원소를 결과값에 append하는 순서에 따라 preorder, inorder, postorder를 구현할 수 있다.

◼ 원소를 저장하는데 list 대신 dictionary 사용

• 처음에는 list를 사용하여 원소값을 입력 받았으나 이진트리의 모양을 몰라서 정확한 인덱스 범위를 설정할 수 없기 때문에 dictionary를 사용하여 원소를 입력받음