[BaekJoon] 2263 트리의 순회 (Java)

1.  문제 링크

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

2.  문제

요약

• n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지 번호가 중복없이 매겨져 있습니다.
• 이진트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 n이 주어지고 두 번째 줄에는 인오더를 나타내는 n개의 자연수가 주어지며 세 번째 줄에는 포스트오더가 주어집니다.
• 출력: 첫 번째 줄에 프리오더를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n, index;
    static int[] post, in, pre;
    static void input() {
        Reader scanner = new Reader();
        n = scanner.nextInt();
        post = new int[n];
        in = new int[n];
        pre = new int[n];

        for(int idx = 0; idx < n; idx++)
            in[idx] = scanner.nextInt();

        for(int idx = 0; idx < n; idx++)
            post[idx] = scanner.nextInt();
    }

    static void solution() {
        index = 0;
        preOrder(0, n - 1, 0, n - 1);

        StringBuilder sb = new StringBuilder();
        for(int node : pre) sb.append(node).append(' ');

        System.out.println(sb);
    }

    static void preOrder(int inStart, int inEnd, int postStart, int postEnd) {
        if(inStart <= inEnd && postStart <= postEnd) {
            pre[index++] = post[postEnd];

            int root = inStart;
            for(int idx = inStart; idx <= inEnd; idx++) {
                if(in[idx] == post[postEnd]) {
                    root = idx;
                    break;
                }
            }

            preOrder(inStart, root - 1, postStart, postStart + root - inStart - 1);
            preOrder(root + 1, inEnd, postStart + root - inStart, postEnd - 1);
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}