import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
#root 에서 i-start 는 inorder 에서 preorder 와 같은 값을 가지기 위해 이동한 범위이고
#이후 +1 을 하면 오른쪽 서브트리의 시작점이 된다
def Postorder(root,start,end):
for i in range(start,end):
if inorder[i]==preorder[root]:
Postorder(root+1 ,start, i) # inorder의 왼쪽 부분
Postorder(root+1+(i-start) , i+1 , end) #inorder의 오른쪽 부분
answer.append(preorder[root])
for i in range(int(input())):
N=int(input())
preorder=list(map(int,input().split()))
inorder=list(map(int,input().split()))
answer=[]
Postorder(0,0,N)
print(*answer)📌 어떻게 접근할 것인가?
전위순회와 중위순회의 결과가 주어졌을때 후위순회를 출력하는 문제이다.
- 3 6 5 4 8 7 1 2
5 6 8 4 3 1 2 7
위와 같이 입력을 받았다고 하자. 첫번째가 전위순회 , 두번째가 중위순회이다.
전위순회에서 순서대로 탐색했을때 각 노드는 부모노드가 된다.
3은 6 7의 부모노드이고 6은 5 4 의 부모노드이다.
또한 중위순회에서 전위순회가 가진 부모노드를 기준으로 왼쪽노드 오른쪽 노드가 나뉘어진다.
만약 처음 전위순회의 첫번째 값인 (루트노드) 3이라 해보자.
중위순회에서 3이 위치한 기준으로 양옆을 나누면 [ 5 , 6 , 8 , 4 ] , [ 1 , 2 , 7 ] 로 나뉘게 된다.
즉 3을 부모노드 기준으로 봤을때 왼쪽노드와 오른쪽 노드로 나눌수 있게된다.
따라서 조건문을 다음과 같이 작성한다.
if inorder[i]==preorder[root]
전위순회의 부모값이 중위순회의 값과 같을때 그때를 기점으로 중위순회를 왼쪽과 오른쪽으로 나눈다.
따라서 총 2번을 탐색한다.
- Postorder(root+1 ,start, i) # inorder의 왼쪽 부분
- Postorder(root+1+(i-start) , i+1 , end) #inorder의 오른쪽 부분
[ 5 6 8 4 3 1 2 7 ] 이 있을때 3을 기준으로
왼쪽 부분은 [ 5 , 6 , 8 , 4 ] - root + 1
오른쪽 부분은 [ 1 , 2 , 7 ] - root + 1 + ( i - start )
를 의미한다.
i-start 는 5 6 8 4 3 까지 이동한 후에 총 이동거리 ( 5 ) 가 되고
이후 다음 1부터 탐색하기 위해 + 1 을 해야하므로
오른쪽 부분은 root + 1 + ( i - start ) 가 된다.
