#유형 : 트리, 자료구조
#난이도 : 골드 3
# 1) postOrder의 마지막 원소가 트리의 루트라는 특징을 이용하여 inOrder(좌우로 나뉜다는 특징)에서
1. 첫번째 인덱스 ~ 해당 인덱스-1 //// 2. 해당 인덱스+1 ~ 마지막 인덱스 로 분할 한다.
# 2) postOrder를 다음과 같이 분할
1. 후위 배열의 첫번째 인덱스 ~ 찾은인덱스 - 중위순회에서의 첫 인덱스 - 1
2. 후위 배열의 첫번째 인덱스 + 찾은인덱스 - 중위순회에서의 첫 인덱스 ~ 마지막 인덱스 -1 로 나누어준다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
package bj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class p2263 {
static int N;
static int in[],post[],idx[];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
in = new int[N+1];
post = new int[N+1];
idx = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
in[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
post[i] = Integer.parseInt(st.nextToken());
}
for(int i=1; i<=N; i++)
idx[in[i]] = i;
preOrder(0, N, 0, N);
}
public static void preOrder(int in_begin, int in_end, int post_begin, int post_end) {
if(in_begin > in_end || post_begin > post_end || post_end == 0)
return;
int root = post[post_end];
System.out.print(root+" ");
int left = idx[root] - in_begin;
//Left
preOrder(in_begin, idx[root] - 1, post_begin, post_begin + left -1);
//right
preOrder(idx[root] + 1, in_end, post_begin + left, post_end - 1);
}
}
|
cs |
'백준' 카테고리의 다른 글
| #백준_13549 숨바꼭질 3 - Java 자바 (0) | 2020.04.25 |
|---|---|
| #백준_12851 숨바꼭질 2 - Java 자바 (0) | 2020.04.24 |
| #백준_5639 이진 검색 트리 - Java 자바 (0) | 2020.04.22 |
| #백준_9663 N-Queen - Java 자바 (0) | 2020.04.21 |
| #백준_1058 친구 - Java 자바 (0) | 2020.04.17 |
