20180826 8월 BOJ 풀이 : 트리의 순회

트리의 순회

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

트리에서 주는 힌트는 두 가지이다. 중위순회로 들어오는 목록과 후위순회로 들어오는 목록이 있는 것이다. 처음에 이를 가지고 전위순회를 출력하라고 하길래 이게 가능한가 싶기도 했다. 하지만 직접 손으로 해보니 가능하더라; 

이 문제를 풀기 위해선 역시 순회에 대한 기본적인 개념이 머릿속에 있는 상태에서 풀어야 하는데 나 역시도 직접 해보니 어려웠다. 후위순회의 경우에는 항상 해상 서브트리의 맨 오른쪽 값이 루트를 취하는 것에 착안하여 재귀적이 형태로 생각해볼 수 있었다.

(1) 후위순회 리스트에서 가장 마지막 인덱스는 루트이다.

(2) (1) 에서 구한 루트 값을 가지고 중위순회를 루트를 기준으로 왼쪽 서브트리, 오른쪽 서브트리로 나눈다.

여기서 왼쪽과 오른쪽 서브트리는 어떻게 나누느냐? 하는 의문이 생긴다.

O(n) 으로 중위순회 값을 탐색하면서 루트 값임을 판별하면 루프를 빠져나오는 형태로 하고, 이후에 시작값과 루트가 있는 인덱스의 차이를 구한다. 이 값의 차이는 루트를 기준으로 하는 왼쪽 서브트리의 노드 개수이다.

(3) (2) 를 통해서 왼쪽 서브트리의 노드 개수를 구하게 되면 재귀적인 형태를 생각해볼 수 있는데

왼쪽 서브트리에서의 중위순회, 후위순회

오른쪽 서브트리에서의 중위순회, 후위순회 

각각의 목록을 새롭게 시작값과 끝값을 계산하는 것이다.

말보단 코드를 보자.

import java.io.*;
import java.util.*;
 
public class Main {
 
    static InputStreamReader isr;
    static BufferedReader br;
    static OutputStreamWriter osw;
    static BufferedWriter bw;
    static StringTokenizer st;
    
    static int[]inArr = null;
    static int[]postArr = null;
    static int s = 0;
    static int e = 0;
    
    public static void main(String[] args) throws IOException {
        isr = new InputStreamReader(System.in);
        br = new BufferedReader(isr);
        osw = new OutputStreamWriter(System.out);
        bw = new BufferedWriter(osw);
 
        int n = Integer.parseInt(br.readLine());
        inArr = new int[n+1];
        postArr = new int[n+1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++)
            inArr[i] = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i <= n; i++)
            postArr[i] = Integer.parseInt(st.nextToken());
        
        process(bw, 1, n, 1, n);
        
        bw.close();
        br.close();
    }
    
    private static void process(BufferedWriter bw, int inOrderStart, int inOrderEnd, int postOrderStart, int postOrderEnd) throws IOException{
        
        if(inOrderStart > inOrderEnd || postOrderStart > postOrderEnd)
            return;
        
        int root = postArr[postOrderEnd];
        
        int left = 0;
        
        for(int i = inOrderStart; i <= inOrderEnd; i++){
            if(inArr[i] == root){
                left = i - inOrderStart;
                break;
            }
        }
        
        bw.write(root + " ");
        
        process(bw, inOrderStart, inOrderStart + left - 1, postOrderStart, postOrderStart + left - 1);        // 왼쪽 서브트리
        process(bw, inOrderStart + left + 1, inOrderEnd, postOrderStart + left, postOrderEnd - 1);            // 오른쪽 서브트리
        
    }
}