#백준_2263 트리의 순회 - Java 자바

#유형 : 트리, 자료구조

#난이도 : 골드 3

 

# 1) postOrder의 마지막 원소가 트리의 루트라는 특징을 이용하여 inOrder(좌우로 나뉜다는 특징)에서 
1. 첫번째 인덱스  ~  해당 인덱스-1  //// 2. 해당 인덱스+1  ~ 마지막 인덱스 로 분할 한다.

 

# 2) postOrder를 다음과 같이 분할

1. 후위 배열의 첫번째 인덱스 ~ 찾은인덱스 - 중위순회에서의 첫 인덱스 - 1
2. 후위 배열의 첫번째 인덱스 + 찾은인덱스 - 중위순회에서의 첫 인덱스 ~ 마지막 인덱스 -1 로 나누어준다.

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p2263 {
    static int N;
    static int in[],post[],idx[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        in = new int[N+1];
        post = new int[N+1];
        idx = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            in[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            post[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1; i<=N; i++)
            idx[in[i]] = i;
        
        
        preOrder(0, N, 0, N);
    }
    public static void preOrder(int in_begin, int in_end, int post_begin, int post_end) {
        if(in_begin > in_end || post_begin > post_end || post_end == 0)
            return;
        
        int root = post[post_end];
        System.out.print(root+" ");
        
        int left = idx[root] - in_begin;
                
        //Left
        preOrder(in_begin, idx[root] - 1, post_begin, post_begin + left -1);
        //right
        preOrder(idx[root] + 1, in_end, post_begin + left, post_end - 1);
    }
}