[백준 2263] 트리의 순회(Java)

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

이 문제는 트리의 성질을 이용하여 풀 수 있습니다.

이전에 풀었던 트리 문제(https://velog.io/@gale4739/%EB%B0%B1%EC%A4%80-4256-%ED%8A%B8%EB%A6%ACJava)와 유사한 듯 다르게 접근해야 합니다.

중위 순회와 후위 순회 결과가 나왔을 때 전위 순회 결과를 출력하는 문제로, 각 순회의 특징에 대해 알아야 합니다.

중위 순회의 경우 왼쪽에서 오른쪽으로 탐색하여 루트 노드값을 안다면 그 값을 기준으로 왼쪽은 왼쪽 자식 노드, 오른쪽은 오른쪽 자식 노드가 됩니다.

후위 순회의 경우 리프 노드에서 시작하여 루트 노드까지 탐색합니다. 따라서 맨 마지막에 루트 노드가 나오는 순서로 진행됩니다.

따라서 이를 동시에 적용시킨다면 다음과 같습니다.

1. 후위 순회 결과를 탐색하면서 현재 부모 노드를 체크
2. 부모 노드를 기준으로 중위 순회 배열을 두 개로 나눔
3. 각각의 나눈 배열을 재귀함수를 이용하여 탐색한 결과를 트리의 자식 노드로 설정

이 때 투 포인터로 탐색하여 순회를 진행합니다. 중위 순회 배열과 후위 순회 배열 각각을 가리키는 포인터 두 개를 설정한 후 후위 순회 배열의 끝 포인터가 부모 노드를 가리키기 때문에 그 값을 출력합니다.

이 때 부모 노드가 중위 순회 배열에서 몇 번째에 위치하는지 체크한 후 왼쪽과 오른쪽으로 나누어 재귀함수를 이용하여 탐색합니다.

다음은 코드입니다.

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;
    }
}