[Python] 백준 - 2263 트리의 순회

 

문제

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

입력

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

출력

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

 

 

문제해결방법 - (구글링 참조)

 

1. 문제를 푸는 아이디어는 생각을 했었다. 디테일한 부분은 구글링을 참조해서 도움을 받았다.

 

일단 세가지 순회의 방법은 바로 전 문제에서 참조하면 되는데, 간단히 설명하면 다음과 같다.

 

아래와 같이 문자열이 저장되어있는 트리구조가 있을 때, 

 

<'ABCDEFG' 문자열이 담긴 트리>

 

출력 혹은 탐색 순서

전위순회 -> ABDCEFG

중위순회 -> DBAECFG

후위순회 -> DBEGFCA

 

이 순서로 출력 및 탐색을 한다.

여기에서 이 문제처럼 중위 순회와 후위 순회가 주어졌을 경우, 패턴을 알 수 있다.

 

출력 \  인덱스	0	1	2	3	4	5	6
전위순회(pre)	A	B	D	C	E	F	G
중위순회(in)	( D	B)	A	( E	C	F	G)
후위순회(post)	( D	B)	( E	G	F	C)	A

 

 

1. 후위순회의 맨 끝점은 전위순회의 맨 앞 원소임을 알 수 있다.

2. 중위순회에서 후위순회 마지막 원소(전위순회 맨 앞 원소)를 기준으로 분할한다. (왼쪽자식/오른쪽자식)

3. 왼쪽자식부터 1번을 반복하고, 그다음 오른쪽자식으로 1번을 반복한다.

 

- 재귀 함수를 구성할 때, 투 포인터로 구현하게 되는데, 좀 헷갈린다.

- 분할되는 리스트의 갯수를 이용해 시작점이나 끝점으로부터 구해준다. 라는 개념으로 접근하면 오류가 없다.

  시작점과 끝점이 정확히 특정되고, 분할되는 노드갯수는 정해져 있기 때문이다.

  (l, r, mid, -1, +1 만 가지고 구성하면 안맞게되는 반례가 생길 수 있음.)

 

왼쪽자식, 오른쪽자식으로 분할될 때 범위

 

- l, r (중위순회리스트) post_l, post_r (후위순회리스트)

 

분할 \ 매개변수	l	r	post_l	post_r
PRE(왼쪽)	시작점	mid-1	post_l	post_l+(왼쪽자식 노드 갯수)-1
PRE(오른쪽)	mid+1	끝점	post_r-(오른쪽자식 노드 갯수)	post_r-1

 

 

쉽게쉽게 생각해서 이런 식으로 매개변수를 구성하면 된다. 

 

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
IN = list(map(int, input().split()))
POST = list(map(int, input().split()))
INDEX = [0 for _ in range(n+1)]
res = []

for i in range(n): # IN 리스트 원소에 해당하는 인덱스에 i를 저장
	INDEX[IN[i]] = i

def PRE(l, r, post_l, post_r):
	if l > r:
		return
	root = POST[post_r]
	res.append(root)
	mid = INDEX[root]
	left = mid-l # 왼쪽 서브트리노드의 갯수
	right = r-mid # 오른쪽 서브트리노드의 갯수
	# 헷갈리면 시작점이나 끝점으로부터 갯수로 접근
	PRE(l, mid-1, post_l, post_l+left-1)
	PRE(mid+1, r, post_r-right, post_r-1)

PRE(0, n-1, 0, n-1)
print(*res)