https://www.acmicpc.net/problem/5639
문제
이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
- 노드의
왼쪽 서브트리에 있는 모든 노드의 키는노드의 키보다 작다. - 노드의
오른쪽 서브트리에 있는 모든 노드의 키는노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도이진 검색 트리이다.
전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다.
후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다.
예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.
입력
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수이다.
모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.
출력
입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.
예제 입력 1
50
30
24
5
28
45
98
52
60
예제 출력 1
5
28
24
45
30
60
52
98
50+) 예제 입력 2
5
4
2
1
3
6
8
7
9+) 예제 출력 2
1
3
2
4
7
9
8
6
5풀이
- 이진 탐색 트리 + 순회 결과 → 순회 결과만으로 트리를 파악할 수 있음!
- 트리의 탐색(문제에서 postOrder)을 범위를 지정해서 할 수도 있음
package tree;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main_5639 {
private static int numberOfNode;
private static int[] nodes = new int[100_000];
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
input();
process();
output();
}
private static void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String node = br.readLine();
int index = 0;
while (node != null && !node.equals("")) {
nodes[index++] = Integer.parseInt(node);
node = br.readLine();
}
numberOfNode = index;
}
private static void process() {
postOrder(0, numberOfNode - 1);
}
private static void postOrder(int start, int end) {
int currentNode = nodes[start];
int startRightNode = end + 1;
if (start > end) {
return;
}
for (int index = start + 1; index <= end; index++) {
if (nodes[index] > currentNode) {
startRightNode = index;
break;
}
}
postOrder(start + 1, startRightNode - 1);
postOrder(startRightNode, end);
sb.append(currentNode).append('\n');
}
private static void output() {
System.out.println(sb);
}
}