[백준] 2263 트리의 순회 -> 트리의 inorder, postorder의 성질을 이해하자

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

2263번: 트리의 순회

 

트리의 순회 중 preorder를 구해야 한다 

우선 preorder, inorder, postorder에 대해서 알아야 한다

preorder : root -> left child -> right child 

inorder : left child -> root -> right child 

postorder : left child -> right child -> root 

 

여기서 주목할 점은 postorder 에서 root가 배열에서 맨 마지막 요소가 될 것이라는 것이다 

예시로 살펴봐도 그렇다 

예시로 주어진 tree는 다음과 같다 

root가 2인 경우이다 

postorder는 1 -> 3 -> 2 

inorder는 1 -> 2 -> 3

여기서 inorder의 성질을 이용하면, 2가 root이면 이를 경계로 왼쪽 오른쪽 나누면 왼쪽 서브트리, 오른쪽 서브트리 순회 결과라고 볼 수 있다 !! 

그리고 나누어진 왼쪽 서브트리와 오른쪽 서브트리에서 각각 재귀적으로 다시 그 안에서 root를 찾고, 왼쪽 (서브)서브트리, 오른쪽 (서브)서브트리를 순회하면 된다. 

preorder 함수 내에서 root에 방문할때마다 print 하면 따로 preorder result를 저장하지 않아도 되어서 메모리를 절약할 수 있다. 

 

position 배열은,

position[inorder의 node 값]  = 해당 node의 배열 내에서 index

를 저장한 배열이다.

preorder 함수 내에서 재귀호출 시, left subtree와 right subtree 순회를 위해, index를 쉽게 알기 위해 필요하다. 

 

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

n = int(input())
position = [0]*(n+1)

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

for i in range(n):
    position[inorder[i]] = i
# preorder : root -> left child -> right child

def preorder(in_start, in_end, post_start, post_end):
    # 재귀 종료 조건 - start와 end 가 만나는 지점에서 종료
    if (in_start > in_end) or (post_start > post_end):
        return
    root = postorder[post_end]
    print(root, end=" ") # root

    left = position[root] - in_start
    right = in_end - position[root]
    # left child
    preorder(in_start, in_start+left-1, post_start, post_start+left-1)
    # right child
    preorder(in_end-right+1, in_end, post_end - right, post_end-1)

preorder(0, n-1, 0, n-1)