[Today I Learned 07] 2. 백준(#2263)
트리 순회에 대해 공부하던 도중 중위 순회와 후위 순회의 값을 주고 전위 순회로 바꾸는 문제를 마주 했다. 트리 순회에 대해서 다 이해했다고 생각했는데 막상 문제를 마주하니깐 어떻게 풀어야 될지 감이 잡히지 않았다. 그래서 답을 보고 이해한 대로 작성해보려고 한다.
1. 트리 순회(#2263)
문제
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
출력
첫째 줄에 프리오더를 출력한다.
접근 방법
1. 후위 순회 값의 마지막 숫자는 전체 루트이다.
2. 중위 순회는왼쪽, 루트, 오른쪽
순으로 작성되기 때문에 후위 순회에서 찾은 루트 값을 이용해서 왼쪽 트리와 오른쪽 트리의 노드 수를 구할 수 있다.
3. 찾은 왼쪽 노드 수와 오른쪽 노드 수를 이용하여 중위 순회를왼쪽 트리, 루트, 오른쪽 트리
로 나눌 수 있다.
4. 동일하게 후위 순회를 왼쪽 트리, 오른쪽 트리, 루트로 나눌수 있다.
5. 이러한 과정을 재귀로 반복한다.
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
input = stdin.readline
# 노드 개수
n = int(input())
# 중위 순회 결과 값
inorder = list(map(int, input().split()))
# 후위 순회 결과 값
postorder = list(map(int, input().split()))
# 중위 순회 각 노드 인덱스
index = [0] * (n + 1)
for i in range(n):
index[inorder[i]] = i
# 전위 순회로 바꾸는 함수
def preorderset(inStart, inEnd, poStart, poEnd):
if inStart > inEnd or poStart > poEnd: return
# 트리의 루트
root = postorder[poEnd]
# 루트의 인덱스
root_idx = index[root]
# 전위 순회는 '루트-왼쪽-오른쪽'이기 때문에 바로 루트 출력
print(root, end=' ')
# 왼쪽 노드 개수
left = root_idx - inStart
# 오른쪽 노드 개수
right = inEnd - root_idx
# 왼쪽 트리 재귀
preorderset(inStart, root_idx - 1, poStart, poStart + left - 1)
# 오른쪽 트리 재귀
preorderset(root_idx + 1, inEnd, poEnd - right, poEnd - 1)
preorderset(0, n - 1, 0, n - 1)
Author And Source
이 문제에 관하여([Today I Learned 07] 2. 백준(#2263)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunchanpark/Today-I-Learned-07-2.-백준2263저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)