[백준 2263번] 트리의 순회

문제 링크 >> https://www.acmicpc.net/problem/2263

 

 

📋 문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다.

이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

 

👉 입력

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

 

 

👈출력

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

 

 

💡 사용된 개념

✔️ 트리의 순회

• 전위순회(preorder) : 루트노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
• 중위순회(inorder) : 왼쪽 서브 트리 -> 루트노드 -> 오른쪽 서브 트리
• 후위순회(postorder) : 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트노드

 

 

📝 풀이

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def preorder(i_s, i_e, p_s, p_e):
  if i_s > i_e or p_s > p_e:
    return
  
  root = postorder[p_e]
  print(root, end=" ")
  
  preorder(i_s, tree[root] - 1, p_s, p_s + tree[root] - i_s - 1)
  preorder(tree[root] + 1, i_e, p_s + tree[root] - i_s, p_e - 1)

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

tree = [0] * (n+1)
for i in range(n):
  tree[inorder[i]] = i
  
preorder(0, n-1, 0, n-1)

 

인오더와 포스트오더를 보고 프리오더를 구하는 문제였다.

프리오더를 구하기 위해 인오더와 포스트오더에서 뽑아내야 할 특징은 다음과 같다.

 

• 인오더 : 루트가 중간에 위치하고 루트의 왼쪽은 왼쪽 서브 트리, 루트의 오른쪽은 오른쪽 서브 트리이다.
• 포스트오더 : 루트 노드가 가장 마지막에 위치한다.

 

n, inorder, postorder를 각각 입력받고 난 이후 가장 먼저 할 일은 중위순회 값들의 인덱스를 저장하는 것이다.

이는 후위순회를 살펴볼 때 루트가 어디에 위치하고 있는지 알아보기 위함이다.

 

함수 preorder에서 먼저 재귀함수를 탈출하기 위해 조건을 설정한다.

그리고 전위순회이기 때문에 postorder의 제일 마지막에 위치한 루트를 찾아 출력한다.

 

이후 각각 왼쪽과 오른쪽 서브 트리를 방문한다.