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

트리의 순회

https://velog.io/@estry/%EB%B0%B1%EC%A4%80-4256%EB%B2%88-%ED%92%80%EC%9D%B4

이전에 풀었던 것은 프리오더와 인오더로 순회한 결과가 주어졌을 때 포스트 오더로 순회한 결과를 구하는 것이었다면 이번에는 인오더와 포스트오더로 순회한 결과를 가지고 프리오더 순회한 결과를 구하는 것이다.

처음에는 전에 풀었던 방식을 적용해서 풀어보려고 했다. 하지만 재귀과정에서 index가 꼬이는 문제가 있어 다른 방법을 생각했다.

중요한 것은 포스트오더한 결과의 가장 마지막이 루트 노드라는 것이다.

이 사실을 알고 나면 그 다음은 편했다. 루트 노드를 찾아내면 인오더 결과에서 루트 노드를 기준으로 좌측은 좌 서브트리, 우측은 우 서브트리이다.

좌 서브트리의 루트 노드의 인덱스는 루트 노드의 인덱스에서 1을 뺀 것과 같다. 우 서브트리는 포스트오더 루트 노드의 위치에서 1 뺀 것과 같다.

이를 식으로 표현하면

포스트오더에서 좌 서브트리의 끝 = 좌 서브트리의 root index
= postorder start index + root index - inorder start index -1
포스트오더에서 우 서브트리의 끝 = 우 서브트리의 root index
= postorede end index - 1

와 같다.

또 우 서브트리의 시작 위치를 찾아줘야는데 우 서브트리의 시작 위치는 좌 서브트리의 길이만큼 이동한 위치에서 시작한다.

따라서

next postoredr start index =
postorder start index + root index - inorder start index

와 같다.

코드

import java.io.*;
import java.util.ArrayList;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int ans = 0;
    static int n, m, k;
    static boolean[][] visit;
    static int[][] graph;
    static int[] inorder;
    static int[] postorder;
    static ArrayList<Integer> preorder;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        String[] in = br.readLine().split(" ");
        String[] post = br.readLine().split(" ");
        inorder = new int[n];
        postorder = new int[n];
        preorder = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            inorder[i] = Integer.parseInt(in[i]);
            postorder[i] = Integer.parseInt(post[i]);
        }
        preOrder(0,n-1,0, n-1);

        for (int i = 0; i < n - 1; i++) {
            System.out.print(preorder.get(i) + " ");
        }
        System.out.print(preorder.get(n - 1));
        br.close();
        bw.close();
    }

    private static void preOrder(int is, int ie, int ps, int pe) {
        if (is > ie || ps > pe)
            return;
        int root = postorder[pe];
        preorder.add(root);
        int rootIdx = 0;
        for (int i = 0; i < n; i++) {
            if(inorder[i] == root) {
                rootIdx = i;
                break;
            }
        }
        preOrder(is, rootIdx - 1, ps, ps + rootIdx - is -1);
        preOrder(rootIdx+1, ie, ps + rootIdx - is, pe - 1);
    }
}