[백준, BOJ 2263] 트리의 순회 (java)

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

2263번: 트리의 순회

---

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

728x90

 

예제 입력 1

3
1 2 3
1 3 2

예제 출력 1

2 1 3

---

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

public class Main {
	
	static StringBuilder sb;
	static int n;
	static int[] inOrder;
	static int[] postOrder;
	
	private static void preOrder(int is, int ie, int ps, int pe) {
		
		if(is > ie) return;
		
		// 포스트오더의 가장 마지막은 프리오더의 가장 처음
		sb.append(postOrder[pe] + " ");
		
		// 인오더에서 pe를 찾는다
		int parent = 0;
		for (int i = is; i <= ie; i++) {
			if(inOrder[i] == postOrder[pe]) {
				parent = i;
				break;
			}
		}
		
		// 인오더에서 pe를 기준으로 왼쪽 서브트리 개수와 오른쪽 서브트리 개수
		int leftCount = parent - is;
		int rightCount = ie - parent;
		
		// pe를 기준으로 왼쪽 서브트리, 오른쪽 서브트리 재귀
		preOrder(is, parent - 1, ps, ps + leftCount - 1);
		preOrder(parent + 1, ie, pe - rightCount, pe - 1);
	}

	public static void main(String arg[]) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		sb = new StringBuilder();
		
		// 입력
		n = Integer.parseInt(br.readLine());
		
		inOrder = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			inOrder[i] = Integer.parseInt(st.nextToken());
		}
		
		postOrder = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			postOrder[i] = Integer.parseInt(st.nextToken());
		}
		
		// 프리오더 구하기
		preOrder(0, n - 1, 0, n - 1);
		
		// 출력
		System.out.println(sb);
	}
}