2263_트리의 순회 (메모리초과 나온다면?)

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

 

이번에는 트리의 순회 문제였다.

 

트리 구조를 보면 특징이 하나있다. 바로 트리를 잘라서 봐도 트리구조란 것

 

이전 문제에서 본 트리를 잠깐 보자면, 하나의 큰 트리는 작은 트리로 쪼갤 수 있다. 지금은 A가 루트인 트리이지만 C가 최고위의 트리와 B가 최고위인 트리 두개가 합쳐진 형태라고도 볼 수 있다.

 

그리고 전위,중위,후위 탐색은 특징이 있다.

 

전위 : 루트 + 왼쪽 + 오른쪽

중위 : 왼쪽 + 루트 + 오른쪽

후위 : 왼쪽 + 오른쪽 + 루트

 

이다. 이를 활용해서 루트와 왼쪽,오른쪽을 뽑아낼 수 있다면 전위탐색을 추출해낼 수 있다.

 

전위탐색은 루트 노드를 가장 먼저 출력하고 왼쪽,오른쪽을 출력하는데 이를 생각해보면 왼쪽을 출력할때도

 

왼쪽 트리 즉, B-D로 이루어진 서브트리의 루트를 출력하고 D로 이루어진 하나의 트리의 루트를 출력함을 알 수 있다.

 

오른쪽탐색또한 C-E.F -G 로 이루어진 트리에서 C를 뽑고 이 트리의 왼쪽은 E로만 이루어진 트리가 나오는것을 알 수 있다.

 

그리고 우리한테는 중위,후위탐색한 결과물이 있다.

 

우리는 결국 0~n-1번 노드를 가진 트리를 가진건데, 후위탐색에서 끝 부분은 루트 노드임으로 루트노드를 가져올 수 있다. 또한 이 루트노드가 중위탐색에서 몇번째에 위치한지 알아낸 후, 왼쪽과 오른쪽으로 나누면 서브 트리가 어디서 분류되는지 알 수 있다.

 

이를 재귀형식으로 반복하면 전위탐색을 출력할 수 있다.

 

 

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
n = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))

pos = [0] * (n+1)
for i in range(n):
    pos[inorder[i]] = i

def f(in_start,in_end,p_start,p_end):

    if (in_start > in_end) or (p_start > p_end):
        return

    parents = postorder[p_end]
    print(parents,end=' ')

    left = pos[parents]-in_start
    right = in_end - pos[parents]

    f(in_start,in_start+left-1,p_start,p_start+left-1)
    f(in_end-right+1,in_end,p_end-right,p_end-1)

f(0,n-1,0,n-1)

 

 

처음에 코드가 자꾸 메모리 부족으로 안떳는데 이는 파이썬의 특징이다. 재귀limit를 sys.sterecursion으로 너무 많이 늘려주면, 재귀제한은 풀리지만 파이썬 자체의 메모리제한이 걸리게 된다. 그렇기에 재귀제한을 10**5 정도로 걸면 재귀에러도 안뜨고 메모리제한에도 안걸릴 수 있다.