[백준] 2263 : 트리의 순회

www.acmicpc.net/problem/2263

2263번: 트리의 순회

---

• 특정 트리에서 post order 순회 시 루트 값이 반드시 마지막에 나오게 된다.
• in order 순회는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 보기 때문에, post order 에서 찾은 루트 값을 통해 왼쪽과 오른쪽 서브트리를 구분할 수 있다.
• 재귀마다 루트를 먼저 확인해주고, 해당 루트를 기준으로 in order 와 post order 에서의 서브트리들을 호출해준다.
• post order 는 왼쪽 서브트리, 오른쪽 서브트리 순으로 찍기 때문에, in order 에서 왼쪽 서브트리의 사이즈를 확인한다면 동일하게 인덱싱하여 구분할 수 있다.
• 파이썬으로 푼다면 sys 의 재귀 한도를 늘려줘야 백준에서 RecursionError 가 나지 않는다. 시간 엄청 버렸다...

---

import sys
sys.setrecursionlimit(10**6)                    # 재귀 호출 깊이 설정

n = int(input())

inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

rootidx = [0] * (n+1)                           # 재귀호출시 현재 루트 값에 대한 인덱스 정보
for i in range(n):
    rootidx[inorder[i]] = i

def subtree(inl, inr, pol, por):                # 매 서브트리마다
    if inl > inr or pol > por:                  # 빈 트리일 시 종료
        return
        
    rt = postorder[por]                         # 루트값은 반드시 post 의 마지막 인덱스
    lsize = rootidx[rt] - inl                   # 왼쪽 서브트리의 크기
    
    print(rt, end=" ")                          # preorder, 루트 먼저 찍어준 뒤
    subtree(inl, rootidx[rt] - 1, pol, pol + lsize - 1) # 왼쪽 서브트리 호출
    subtree(rootidx[rt] + 1, inr, pol + lsize, por - 1) # 오른쪽 서브트리 호출

subtree(0, n-1, 0, n-1)
print()