[Baekjoon] 2263번 : 트리의 순회

1. 문제

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

• 트리 문제

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

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

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

// 예제 입력 1 
3
1 2 3
1 3 2

// 예제 출력 1 
2 1 3

2. 핵심 아이디어

• PostOrder에서 부모 노드를 찾음
• 부모 노드는 InOrder에서 기준점이 되어 좌우를 나눔
• 좌우를 순회하며 과정을 반복

3. Python 문제풀이

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

n = int(input())
inOrder = list(map(int, input().split()))
postOrder = list(map(int, input().split()))
arr = [0 for i in range(n+1)]

for i in range(n) :
  arr[inOrder[i]] = i

def post(start1, end1, start2, end2) :
  if start1 > end1 or start2 > end2 :
    return
  parent = postOrder[end2]
  print(parent, end = " ")

  left = arr[parent] - start1
  right = end1 - arr[parent]

  post(start1, start1+left-1, start2, start2+left-1)
  post(end1-right+1, end1, end2-right, end2-1)

post(0, n-1, 0, n-1)

4. Java 문제풀이