[백준] 2263 트리의 순회 -> 트리의 inorder, postorder의 성질을 이해하자
https://www.acmicpc.net/problem/2263
2263번: 트리의 순회
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
www.acmicpc.net
트리의 순회 중 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는 다음과 같다
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)