<Algorithm> 56. 2263번 트리의 순회

1. 2263번 트리의 순회

• 트리 순회 문제, 전위 후위 중위 순회를 정확하게 알고 있어야 풀 수 있는 문제

• 중위 순회의 순서와 후위 순회의 값을 이용하여 전위 순회에 접근 할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int[] idx = new int[100001];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] inOrder = new int[N];
        int[] postOrder = new int[N];
        
        
        for(int j = 0; j < 2; j ++) {
            st = new StringTokenizer(br.readLine());    
            for(int i = 0; i < N; i ++) {
                int temp =Integer.parseInt(st.nextToken());
                if(j == 0) {
                    idx[temp] = i;                    
                }
                else {
                    postOrder[i] = temp;
                }
                    
            }
        }
        
        pre(0, N, 0, N, postOrder);
        
    }
    public static void pre( int inorderStart, int inorderEnd, int postStart, int postEnd, int[] postorder ) {
        if(inorderStart == inorderEnd) return;
        
        int root = postorder[postEnd - 1];
        // 루트의 값
        int index = idx[root];
        // inorder에서 루트의 순서 
        System.out.print(root + " ");
        int left = index - inorderStart;
        // 왼쪽의 길이
        pre(inorderStart, index, postStart, postStart + left, postorder);
        //post값 -> inorder에서의 순서 -> 순서 -1의 post 값이 출력값
        pre(index + 1, inorderEnd, postStart + left , postEnd - 1, postorder);
           //왼쪽 탐색이 끝나면 바로 오른쪽 탐색해서 출력
     }
    
}