[BOJ] #2263 트리의 순회

트리의 순회

백준 #2263

---

📌 문제

예제 입력

3
1 2 3
1 3 2

예제 출력

2 1 3

---

📌 풀이

Logic

• 정점 개수 N 입력 받기
• inorder, postorder 입력 받기
  • inorder: 루트의 위치를 찾아서 left / right 경계를 나누는 용도
    • left -> root -> right
  • postorder: postorder의 마지막 요소는 트리의 root
    • left -> right -> root
• preorder stack 생성 <- LIFO 이므로 반대로 삽입
  • [in 시작 idx, in 끝 idx, post 시작 idx, post 끝 idx]

# 변수명
n : 노드 개수
inorder, postorder, preorder : 각 방식의 리스트
inorder_index : 각 값의 인덱스를 찾기 위한 딕셔너리
left_size : 현재 서브트리에서 root 기준 왼쪽 노드 수

Python

import sys
input = sys.stdin.readline

n = int(input().strip())

inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

# inorder에서 각 값의 인덱스를 빠르게 찾기 위해 딕셔너리를 사용
inorder_index = [0] * (n + 1)

for i, value in enumerate(inorder):
    inorder_index[value] = i

preorder = []

stack = [(0, n - 1, 0, n - 1)]

while stack:
    in_left, in_right, post_left, post_right = stack.pop()

    if (in_left > in_right):
        continue

    # postorder의 마지막 요소는 항상 트리의 루트
    root = postorder[post_right]
    preorder.append(root)

    # 루트의 인덱스를 inorder에서 찾아서 왼쪽과 오른쪽 서브트리의 크기를 계산
    root_index = inorder_index[root]
    left_size = root_index - in_left

    # 스택은 LIFO -> 오른쪽을 먼저 넣고 왼쪽을 나중에 append
    # 실제 처리 순서는 root -> left -> right
    if (root_index + 1 <= in_right):
        stack.append(
            (
                root_index + 1,
                in_right,
                post_left + left_size,
                post_right - 1,
            )
        )

    if (in_left <= root_index - 1):
        stack.append(
            (
                in_left,
                root_index - 1,
                post_left,
                post_left + left_size - 1,
            )
        )

print(" ".join(map(str, preorder)))

---

✏️ 새로운 내용

enumerate()

반복 가능한 객체를 순회할 때, 인덱스와 값을 함께 꺼내는 함수

• for i, v in enumerate(arr) 형태로 많이 사용함
• 기본 인덱스 시작값은 0이고, start 옵션으로 시작값 변경 가능

arr = [10, 20, 30]

for idx, value in enumerate(arr):
    print(idx, value)
# 0 10
# 1 20
# 2 30

for idx, value in enumerate(arr, start = 1):
    print(idx, value)
# 1 10
# 2 20
# 3 30

---

📚 회고

💡 이진 트리

• '알고리즘' 수업 중 학습 중인 이진 트리의 학습을 위해 풀어보았다.
• in, post, pre의 순회 순서가 매번 헷갈려서 이번 포스트의 그림을 종종 참고해야겠다.