문제 링크 : https://www.acmicpc.net/problem/2263
이 문제는 트리의 성질을 이용하여 풀 수 있습니다.
이전에 풀었던 트리 문제(https://velog.io/@gale4739/%EB%B0%B1%EC%A4%80-4256-%ED%8A%B8%EB%A6%ACJava)와 유사한 듯 다르게 접근해야 합니다.
중위 순회와 후위 순회 결과가 나왔을 때 전위 순회 결과를 출력하는 문제로, 각 순회의 특징에 대해 알아야 합니다.
중위 순회의 경우 왼쪽에서 오른쪽으로 탐색하여 루트 노드값을 안다면 그 값을 기준으로 왼쪽은 왼쪽 자식 노드, 오른쪽은 오른쪽 자식 노드가 됩니다.
후위 순회의 경우 리프 노드에서 시작하여 루트 노드까지 탐색합니다. 따라서 맨 마지막에 루트 노드가 나오는 순서로 진행됩니다.
따라서 이를 동시에 적용시킨다면 다음과 같습니다.
이 때 투 포인터로 탐색하여 순회를 진행합니다. 중위 순회 배열과 후위 순회 배열 각각을 가리키는 포인터 두 개를 설정한 후 후위 순회 배열의 끝 포인터가 부모 노드를 가리키기 때문에 그 값을 출력합니다.
이 때 부모 노드가 중위 순회 배열에서 몇 번째에 위치하는지 체크한 후 왼쪽과 오른쪽으로 나누어 재귀함수를 이용하여 탐색합니다.
다음은 코드입니다.
import java.util.*;
import java.io.*;
class Main {
static BufferedReader br;
static int N;
static StringBuilder sb = new StringBuilder();
static int[] inorder, postorder;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
inorder = getOrder();
postorder = getOrder();
preOrder(0, N - 1, 0, N - 1);
System.out.println(sb);
}
static void preOrder(int is, int ie, int ps, int pe) {
if (is > ie || ps > pe) return;
int curr = postorder[pe];
sb.append(curr).append(" ");
int currIdx = getIndex(curr);
int left = currIdx - is;
preOrder(is, currIdx - 1, ps, ps + left - 1);
preOrder(currIdx + 1, ie, ps + left, pe - 1);
}
static int getIndex(int target) {
for (int i = 0; i < inorder.length; i++) {
if (target == inorder[i]) return i;
}
return -1;
}
static int[] getOrder() throws Exception {
int[] res = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) res[i] = Integer.parseInt(st.nextToken());
return res;
}
}