[백준/BOJ]#2263:트리의 순회 [트리/분할정복/파이썬/python]

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

2263번: 트리의 순회

인오더와 포스트오더 (inorder, postorder)를 입력으로 받으면 

preorder(프리오더)를 출력해주는 문제다.

트리의 순회방법_ 전위, 중위, 후위 순회 방식이다.

 

위의 트리 예시들을 읽어보면 대략적으로 그림이 그려진다. 

Preorder는 맨처음에 루트(부모)가 들어오고, postorder는 맨마지막에 들어온다.

이를 이용하여 처음에 루트를 구한다.

Inorder는 왼쪽부터 쭉 순서대로 순회한다는 것을 알 수 있다.

이를 이용하여 inorder tree를 만들고, 루트를 기준으로 왼쪽 오른쪽을 나눈다. 

바로, 이 방법이 분할정복으로 재귀를 하는 것이다.

 

재귀를 하며 루트를 순서대로 출력하면 루트부터 순회하는 Preorder를 출력할 수 있다.

 

 

 

(메모리초과 문제) 이 문제에서 계속해서 메모리초과 결과가 떠서 애를 좀 먹었다..

그래서 인덱스만 보내는 방법을 썼음에도 불구하고 계속 떠서, array를 dict로 바꾸었지만 계속 메모리초과가 떠서...

맨처음제출코드를 pypy3를 python3로 채점컴파일러를 바꾸니 해결,,,(이럴땐 참 허탈하다..) 어쨌든 해결,, 

 

 

 

 

파이썬코드

#2263_트리의 순회
import sys
sys.setrecursionlimit(10 ** 6)

vertice = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))

def pre(l_in, r_in, l_post, r_post):
    if l_in > r_in or l_post > r_post:
        return
    
    parent = postorder[r_post]
    print(parent, end=" ")
    
    left = tree[parent] - l_in
    right = r_in - tree[parent]

    pre(l_in, l_in+left-1, l_post, (l_post+left)-1)
    pre(r_in-right+1, r_in, r_post-right, r_post-1)
    
tree=[0]*(vertice+1)
for i in range(vertice):
    tree[inorder[i]]=i
pre(0,vertice-1,0,vertice-1)