문제

---

전체 트리와 각 서브트리의 루트노드, 왼쪽 서브트리, 오른쪽 서브트리를 구하는 것이 핵심

순서를 생각했을 때,

포스트 오더의 마지막 노드가 바로 루트 노드이고

인오더에서는 루트 노드를 기준으로 왼쪽이 왼쪽 서브트리, 오른쪽이 오른쪽 서브 트리이다.

다시 포스트 오더로 돌아와 왼쪽 서브트리 부분에서 마지막 노드가 왼쪽 서브트리의 루트 노드, 오른쪽 서브트리의 마지막 노드가 오른쪽 서브트리의 루트 노드이다.

인오더에서 각 서브트리의 루트 노드, 왼쪽 서브트리, 오른쪽 서브트리를 확인한다.

서브 트리가 없을 때까지 위 과정의 반복...

---

Code

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P2263 {

	static int[] inOrder;
	static int[] postOrder;
	
	/*
	 포스트 오더의 마지막 노드가 루트 노드이다.
	 인오더에서 루트 노드의 위치를 기준으로 
	 왼쪽 노드들이 왼쪽 서브 트리 / 오른쪽 노드들이 오른쪽 서브 트리를 이룬다.
	 
	 2개의 각 서브트리도 마찬가지로, 
	 포스트 오더에서 서브트리로 이루어진 부분을 찾고, 거기서 마지막 노드가 서브트리의 루트 노드
	 인오더를 보고 루트 노드를 기준으로 왼쪽, 오른쪽 서브트리로 나눈다.
	 */
	
	/*
	inOrder_index : 각 노드의 인오더에서의 인덱스 
	inOrder_index[inOrder[i]] == i (inOrder의 요소와 인덱스의 대응관계 저장)
	*/
	static int[] inOrder_index;  
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		inOrder = new int[n];
		postOrder = new int[n];
		inOrder_index = new int[n + 1];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < n; i++) {
			inOrder[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < n; i++) {
			postOrder[i] = Integer.parseInt(st.nextToken());
		}
		for(int i = 0; i < n; i++) {
			inOrder_index[inOrder[i]] = i;
		}
		
		getPreOrder(0, n - 1, 0, n - 1);
		System.out.println(sb.toString());
	}
	// in_start : 인오더 시작 인덱스, in_end : 인오더 끝 인덱스
	// post_start : 포스트 오더 시작 인덱스, post_end : 포스트 오더 끝 인덱스
	private static void getPreOrder(int in_start, int in_end, int post_start, int post_end) {
		if(in_start > in_end || post_start > post_end) {
			return;
		}
		int rootNode = postOrder[post_end];
		sb.append(rootNode + " ");
		
		int rootIndex = inOrder_index[rootNode];
		int left_subTree_size = rootIndex - in_start;
		
		// 왼쪽 서브트리
		getPreOrder(in_start, rootIndex - 1, post_start, post_start + left_subTree_size - 1);
		// 오른쪽 서브트리
		getPreOrder(rootIndex + 1, in_end, post_start + left_subTree_size, post_end - 1);
		
		
	}

}

---

참고 : https://velog.io/@abc5259/%EB%B0%B1%EC%A4%80-2263-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%88%9C%ED%9A%8C-JAVA