[백준 2263번] 트리의 순회

mokomoko·2022년 1월 20일

python 백준

1. 문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

제한 사항

시간 : 5 초
메모리 : 128 MB

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

- 키워드

중위 순회와 후위 순회의 특징을 통해 노드를 추출하자.

시간과 메모리의 양을 잘 참고하도록 하자.

2. 풀이

이 문제를 읽었을 때, 지난 번 문제를 잘 생각해봤다.

중위 순회를 보면 부모 노드를 기준으로 왼쪽 오른쪽으로 나눠 지는 것을 볼 수 있고,

후위 순회를 보면 부모 노드는 항상 가장 끝에 있다는 것을 알 수 있다.

이 특징을 통해서 preorder를 구할 수 있다.

다음 테스트케이스를 살펴보자

11
8 4 2 9 5 1 10 6 3 11 7
8 4 9 5 2 10 6 11 7 3 1

후위 순회의 맨 끝에서 부모 노드를 찾고, 중위 순회를 기준으로 나눈다.

전위 순회는 왼쪽 노드의 부모노드부터 탐색하므로 왼쪽 노드의 부모노드를 먼저 찾는다.

이쯤 되면, 무슨 알고리즘을 묻는 것인지 알 것이다.

바로, 분할 정복을 이용해 푸는 것이다.

해당 과정을 계속 진행해보자.

다음 왼쪽 노드에서는 부모 노드가 4고,

자식 노드는 8밖에 남지 않으므로 8이 그 다음으로 들어온다.

오른쪽 노드인 9,5 역시 같은 과정을 거친다.

아까와 같은 경우로 나왔고, 같은 과정을 거치므로

6, 10, 7, 11 순서로 들어온다.

결과로 preorder는 다음과 같이 나온다.

3. 소스코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100001)

preorder = []
inorder = []
postorder = []

# def divide(inorder,postorder): 메모리 초과
# 	if len(inorder) == 1:
# 		preorder.append(inorder[0])
# 	elif inorder and postorder:
# 		for i in range(len(inorder)):
# 			if inorder[i] == postorder[-1]:
# 				preorder.append(postorder[-1])
# 				divide(inorder[:i],postorder[:i])
# 				divide(inorder[i+1:],postorder[i:-1])

def divide(il,ir,pl,pr):
	if ir - il != pr - pl:
		return
	if il < ir and pl < pr:
		for i in range(ir-il):
			if inorder[il+i] == postorder[pr-1]:
				preorder.append(postorder[pr-1])
				divide(il,il+i,pl,pl+i)
				divide(il+i+1,ir,pl+i,pr-1)


def solution():
	divide(0,N,0,N)
	for i in preorder:
		print(i,end=" ")

if __name__ == "__main__":
	N = int(input())
	inorder = list(map(int,input().split()))
	postorder = list(map(int,input().split()))
	solution()