BOJ 2263번: 트리의 순회

www.acmicpc.net/problem/2263

2263번: 트리의 순회

아이디어:

이진트리 / 입력의 첫줄은 inorder = 중위순회, 둘째줄은 postorder = 후위순회.. -> 전위순회 구하기.

중위순회(LVR)

후위순회(LRV) -> 맨 마지막 원소가 루트.

전위순회(VLR) -> 후위순회에서 중위순회를 사용하여 루트를 순서대로 뽑아내면 된다.

중위순회는 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누어지므로, 후위순회[-1](루트)를 중위순회에서 찾고그 인덱스-1까지를 후위순회에서 잘라서 다시 반복한다..

왼쪽 서브트리에서 모두 출력하면 오른쪽 서브트리도 똑같이 반복한다.

 

solve(instart, div-1, poststart, poststart+left-1)

여기서 왜 poststart+left-1을 하는지가 이해가 안됐었다. 나는 div-1이라고 생각했기 때문이다. 그런데, 루트를 기준으로 왼쪽 서브트리를 탐색할때는 저 방법이 상관 없지만 오른쪽 트리를 탐색하는 경우에는 div-1로 하면 인덱스가 맞질 않는다.

그리고 div를 구할때 index함수를 이용했더니 시간초과가 나와서 시간을 단축하기 위해 인덱스 배열을 따로 만들었더니 통과했다.

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

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

index = [0]*(n+1)
for i in range (n):
    index[inorder[i]] = i #root위치 찾는 걸 빠르게 하기 위해서

def solve(instart, inend, poststart, postend):
    if (instart>inend or poststart>postend): return
    root = postorder[postend]
    print(root, end=" ")
    
    #div = inorder.index(root) #중위순회에서 root의 위치
    div = index[root]
    
    left = div - instart #중위순회의 시작인덱스부터 div까지의 거리
    solve(instart, div-1, poststart, poststart+left-1) #왼쪽 서브트리
    solve(div+1, inend, poststart+left, postend-1) #오른쪽 서브트리
    
solve(0,n-1,0,n-1)
    

 

동아리 설명을 위한 허접한 필기..