트리_BOJ #2263: 트리의 순회

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

 

 

---

트리는 재귀로 정의된 자기 참조 자료구조이다.

트리는 특수한 형태의 그래프이 일종이다. 정확히는 순환 구조를 갖지 않는 그래프이다.

 

트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트리이다.

이진 트리는 왼쪽, 오른쪽 최대 2개의 자식을 갖는 매우 단순한 형태이다.

 

이진 트리에는 여러 유형이 있다.

Full Binary Tree: 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.

Complete Binary Tree: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있으며 마지막 레벨의 노드는 가장 왼쪽부터 채워져있다.

Perfect Binary Tree: 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.

 

 

import sys
sys.setrecursionlimit(10**9)
def input():
  return sys.stdin.readline().rstrip()


def get_preorder(in_start, in_end, post_start, post_end):
  # 재귀 종료 조건
  if (in_start > in_end) or (post_start > post_end):
    return
  
  # 후위 순회의 마지막 노드가 서브트리의 루트
  root = postorder[post_end]
  print(root, end=' ')

  # 중위 순회에서 루트 값의 노드가 좌/우 서브트리 구분점
  left = position[root] - in_start
  right = in_end - position[root]

  # 분할 정복
  get_preorder(in_start, in_start+left-1, post_start, post_start+left-1)
  get_preorder(in_end-right+1, in_end, post_end-right, post_end-1)


# 노드의 개수 입력
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

# 후위 순회의 마지막 노드 값이 중위 순회의 어디에 있는지 확인하기 위해 중위 순회 값들의 인덱스를 저장 
position =[0]*(n+1)
for i in range(n):
  position[inorder[i]] = i

# 1부터 n까지의 번호의 노드로 이루어져있으므로 n-1
get_preorder(0, n-1, 0, n-1)