문제 풀이(51)

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

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

/**
 * Solution
 */
public class Main {

    static int n;
    static ArrayList<Integer>inOrder = new ArrayList<>();
    static ArrayList<Integer>postOrder = new ArrayList<>();  
    static HashMap<Integer, Integer>map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            inOrder.add(Integer.parseInt(st.nextToken()));
            map.put(inOrder.get(i), i);
        }

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            postOrder.add(Integer.parseInt(st.nextToken()));
        }

        function(0,n-1,0,n-1);
    }

    public static void function(
    int inOrderStart, int inOrderEnd , 
    int postOrderStart, int postOrderEnd)
    {
        if (inOrderStart > inOrderEnd || postOrderStart > postOrderEnd) {
            return;
        }

        System.out.print(postOrder.get(postOrderEnd)+" ");

        int root = postOrder.get(postOrderEnd);

        int answer = map.get(root);

        int leftLength = answer - inOrderStart;
        

        function(inOrderStart, answer-1, postOrderStart, postOrderStart + leftLength - 1);

        function(answer+1, inOrderEnd, postOrderStart + leftLength, postOrderEnd-1);
    }


}

function 함수:
이 함수는 재귀적으로 호출된다.
포스트오더의 마지막 원소는 현재 서브트리의 루트이다. 이 루트를 출력하고, 인오더에서 이 루트의 위치를 찾아 (이 때, map을 사용하여 빠르게 위치를 찾는다) 왼쪽과 오른쪽 서브트리로 나눈다.
이후, 왼쪽 서브트리에 대한 function 호출과 오른쪽 서브트리에 대한 function 호출을 수행한다. 이 때, 호출 범위를 정확하게 지정하기 위해 인오더와 포스트오더의 시작과 끝 인덱스를 인자로 전달한다.