[JAVA] 백준 - 2263 : 트리의 순회

문제 링크

2263번: 트리의 순회

 

 

풀이 )

  전위, 중위, 후위 순회 시 구조를 보고 풀었다.

• 전위: root ( left ) ( right )
• 중위: ( left ) root ( right )
• 후위: ( left ) ( right ) root

  후위 순회 결과의 마지막이 root이고 이를 이용해서 중위 순회에서의 root 위치를 찾아 좌 우를 나눈다.

  중위 순회에서의 root 위치를 빠르게 찾기 위해 index를 저장하는 배열을 만들었다.

 

import java.io.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] inOrder;
    static int[] postOrder;

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

        int n = Integer.parseInt(br.readLine());
        inOrder = new int[n+1];
        postOrder = new int[n+1];
        index = new int[n+1];

        in = br.readLine().split(" ");
        for(int i = 0; i < n; ++i){
            inOrder[i] = Integer.parseInt(in[i]);
            index[inOrder[i]] = i;
        }
        in = br.readLine().split(" ");
        for(int i = 0; i < n; ++i)
            postOrder[i] = Integer.parseInt(in[i]);
        preOrder(0, n-1, 0, n-1);
        bw.flush();
    }

    static void preOrder(int inSrt, int inEnd, int postSrt, int postEnd) throws IOException {
        if(inSrt > inEnd || postSrt > postEnd)
            return;

        int root = postOrder[postEnd];
        bw.write(root+" ");
        int idx = index[root];
        preOrder(inSrt, idx-1, postSrt, postSrt+(idx-1-inSrt));
        preOrder(idx+1, inEnd, postSrt+(idx-inSrt), postEnd-1);
    }
}

 

주의 )

  인덱스 실수