[JAVA] 백준 2263 트리의순회_탐색

문제 : 

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

 

 

접근 : 

 

  - 인오더와 포스트오더를 저장한다.

 

  - 포스트오더의 마지막 값은 root 노드 이므로 해당 값을 프리오더에 저장하고, 인오더에서 노드의 값을 기점으로 좌우를 나눈다.

 

  - 인오더에서 좌우를 나눈거와 동일한 길이만큼 포스트오더에서 좌우로 나눈다.

 

  - 좌측 나눈 sub 트리에서 위에 과정을 동일하게 반복하고, 오른쪽에 대해서도 동일하게 시행한다.

 

  -결과 값을 출력한다.

 

 

 

 

 

 

 

 

 

코드 구현 : 

 

import java.io.*;

public class Main {
    private static StringBuilder sb;
    private static int[] in_order_idx;
    private static int[] post_order;

    public static void devideTree(int in_start, int in_end, int post_start, int post_end) {
        if(in_start > in_end || post_start > post_end) return;

        int rootNode = post_order[post_end];
        sb.append(rootNode + " ");

        int root_idx = in_order_idx[rootNode];
        int sub_length = root_idx - in_start;

        //왼쪽
        devideTree(in_start, root_idx-1, post_start, post_start+sub_length-1);
        //오른쪽
        devideTree(root_idx+1, in_end, post_start+sub_length, post_end-1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        in_order_idx = new int[n+1];
        post_order = new int[n];

        String[] in_order_str = br.readLine().split(" ");
        String[] post_order_str = br.readLine().split(" ");

        for(int i = 0 ; i < n; i++){
            in_order_idx[Integer.parseInt(in_order_str[i])] = i;
            post_order[i] = Integer.parseInt(post_order_str[i]);
        }

        devideTree(0, n-1, 0, n-1);
        System.out.println(sb);
        br.close();
    }
}