[백준] 2263번 트리의 순회 Java

문제 링크

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

문제

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

입력

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

출력

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

알고리즘: 트리, 분할 정복, 재귀

풀이

tc)
3
1 2 3 => inorder
1 3 2 => postorder

inorder는 루트 노드를 기준으로 왼쪽은 왼쪽 서브 트리, 오른쪽은 오른쪽 서브 트리로 분할 할 수 있다.
postorder은 왼 -> 오 -> 루 이기 때문에 마지막은 루트 노드이고 마지막 - 1번째 노드는 오른쪽 서브 트리의 루트 노드이고, 첫 번째 인덱스 + 왼쪽 서브 트리의 노드 개수 - 1번째 노드는 왼쪽 서브 트리의 루트 노드이다.

ex)
postorder 1 3 2를 보면 2는 루트 노드이다.
inorder 1 2 3에서 루트 노드인 2의 왼쪽은 왼쪽 서브 트리이다. 3은 오른쪽 서브 트리이다.
오른쪽 서브 트리의 postorder은 3이고, inorder은 3이다.
왼쪽 서브 트리의 postorder은 1이고, inorder은 1이다.

그래서 preorder은 2 1 3으로 답을 찾아낼 수 있다.

소스 코드

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

public class Main {
    static int N;
    static int post[], in[], in_ind[];
    static StringBuilder ans = new StringBuilder();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        post = new int[N];
        in = new int[N];
        in_ind = new int[N+1];
        for(int i=0; i<2; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            if(i==0) {
                for(int j=0; j<N; j++) {
                    int v = Integer.parseInt(st.nextToken());
                    in[j] = v;
                    in_ind[v] = j;
                }
            } else if(i==1) {
                for(int j=0; j<N; j++) {
                    int v = Integer.parseInt(st.nextToken());
                    post[j] = v;
                }
            }
        }
        get_pre(0, N-1, 0, N-1);
        System.out.println(ans.toString());
    }
    
    static void get_pre(int in_s, int in_e, int post_s, int post_e) {
        int rt_v = post[post_e];
        ans.append(rt_v + " ");
        
        int rt_ind = in_ind[rt_v];
        if(rt_ind != in_s) {
            get_pre(in_s, rt_ind - 1, post_s, post_s + (rt_ind - 1 - in_s)); //왼쪽
        }
        if(rt_ind != in_e) {
            get_pre(rt_ind + 1, in_e, post_e - (in_e - rt_ind), post_e - 1); //오른쪽
        }
    }
}