문제

풀이

1. 후위순회에서 가장 맨 뒤는 root
2. 중위순회에서 root 위치 찾기
3. root 기준으로 왼쪽 서브트리 오른쪽 서브트리 구분
4. 후위순회에서 왼쪽 서브트리 분리해서 재귀 진행
5. 후위순회에서 오른쪽 서브트리 분리해서 재귀 진행

코드

import java.io.*;
import java.util.*;

public class Main {

    static int n,idx;
    static int[] in,post,pre;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n=Integer.parseInt(br.readLine());
        in=new int[n];
        post=new int[n];
        pre=new int[n];
        String[] inStr=br.readLine().split(" ");
        for(int i=0;i<n;i++)in[i]=Integer.parseInt(inStr[i]);
        String[] postStr=br.readLine().split(" ");
        for(int i=0;i<n;i++)post[i]=Integer.parseInt(postStr[i]);
        preOrder(0,n-1,0,n-1);
        for(int a:pre){
            bw.write(String.valueOf(a));
            bw.write(" ");
        }
        bw.flush();
    }

    static void preOrder(int inStart,int inEnd,int postStart,int postEnd){
        if(inStart>inEnd || postStart>postEnd)return;
        int root=post[postEnd];
        pre[idx++]=root;
        int rootIdx=-1;
        for(int i=inStart;i<=inEnd;i++){
            if(in[i]==root){
                rootIdx=i;
                break;
            }
        }
        preOrder(inStart,rootIdx-1,postStart,postStart+rootIdx-inStart-1);
        preOrder(rootIdx+1,inEnd,postStart+rootIdx-inStart,postEnd-1);
    }

}

#트리