문제
이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다.
아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다.
BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 아래에 C 스타일의 의사 코드로 나와 있다. BT의 노드 v에 대해서, v.left는 왼쪽 자식, v.right는 오른쪽 자식을 나타낸다. v가 왼쪽 자식이 없으면 v.left는 ∅와 같고, 오른쪽 자식이 없으면 v.right는 ∅와 같다.
BT를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다. BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.
예를 들어, 위의 그림을 전위 순회하면 3,6,5,4,8,7,1,2, 중위 순회하면 5,6,8,4,3,1,2,7이 된다. 이를 이용해 후위 순회하면 5,8,4,6,2,1,7,3이 된다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 줄에는 BT를 전위 순회한 결과, 그 다음 줄에는 중위 순회한 결과가 주어진다. 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어진다.
출력
각 테스트 케이스마다 후위 순회한 결과를 출력 한다.
전위 순회는 루트 -> 왼쪽 자식 -> 오른쪽 자식 순으로, 중위 순회는 왼쪽 자식 -> 루트 -> 오른쪽 자식 순으로 순회한다.
전위 순회에서 가장 앞의 값은 트리의 루트이며, 그 다음 값은 루트의 왼쪽 자식이 될 것이다.
그리고 중위 순회에서 루트보다 왼쪽에 있는 값들은 루트의 왼쪽 서브 트리의 값들이고, 오른쪽은 오른쪽 서브 트리의 값이다.
이를 활용하여 코드를 구현하였다.
처음에는 node 클래스를 구현해서 left, right 변수에 재귀적으로 tree를 만들었다.
inOrder에서 index를 빠르게 찾기 위해 map으로 index를 저장하였다.
MyNode root = new MyNode(preOrder[0]); // 전위순회 0번은 항상 root
for (int i = 1; i < N; i++) {
MyNode newNode = new MyNode(preOrder[i]);
makeTree(inOrder.get(root.data), inOrder.get(preOrder[i]), root, newNode);
}
전위 순회에서 0번 노드는 루트이니까 루트를 만들어주고, 1번 index부터 순회하며 새로운 노드를 만들고 root부터 시작해서 자식을 달아주었다.
static void makeTree(int rootIdx, int dataIdx, MyNode root, MyNode data) {
// rootIdx와 자기 자신의 idx는 중위 순회 기준
// 중위 순회에서 x의 index < rootIdx : 왼쪽, 아니면 오른쪽
if (dataIdx < rootIdx) {
// 왼쪽
if (root.left == null)
root.left = data; // 왼쪽 자식이 없으면 추가
else
makeTree(inOrder.get(root.left.data), dataIdx, root.left, data); // 있으면 다시 조사
} else {
// 오른쪽
if (root.right == null)
root.right = data; // 오른쪽 자식이 없으면 추가
else
makeTree(inOrder.get(root.right.data), dataIdx, root.right, data); // 있으면 다시 조사
}
}
중위 순회에서 data의 index가 root의 index보다 작으면 왼쪽, 크면 오른쪽이다. 그리고 왼쪽 자식이 없다면 자식을 추가하면 되고, 자식이 있다면 다시 그 자식 노드를 root로 하여 makeTree를 반복하면 된다.
전체 코드
package Gold.g2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class BOJ_4256_트리 {
static int[] preOrder;
static HashMap<Integer, Integer> inOrder;// value, index
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
int N = Integer.parseInt(br.readLine());
preOrder = new int[N];
StringTokenizer pre = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
preOrder[i] = Integer.parseInt(pre.nextToken());
StringTokenizer in = new StringTokenizer(br.readLine());
inOrder = new HashMap<>();
for (int i = 0; i < N; i++)
inOrder.put(Integer.parseInt(in.nextToken()), i); // value와 index
// 입력
MyNode root = new MyNode(preOrder[0]); // 전위순회 0번은 항상 root
for (int i = 1; i < N; i++) {
MyNode newNode = new MyNode(preOrder[i]);
makeTree(inOrder.get(root.data), inOrder.get(preOrder[i]), root, newNode);
}
postOrder(root);
sb.append("\n");
}
System.out.print(sb.toString());
}
static void makeTree(int rootIdx, int dataIdx, MyNode root, MyNode data) {
// rootIdx와 자기 자신의 idx는 중위 순회 기준
// 중위 순회에서 x의 index < rootIdx : 왼쪽, 아니면 오른쪽
if (dataIdx < rootIdx) {
// 왼쪽
if (root.left == null)
root.left = data; // 왼쪽 자식이 없으면 추가
else
makeTree(inOrder.get(root.left.data), dataIdx, root.left, data); // 있으면 다시 조사
} else {
// 오른쪽
if (root.right == null)
root.right = data; // 오른쪽 자식이 없으면 추가
else
makeTree(inOrder.get(root.right.data), dataIdx, root.right, data); // 있으면 다시 조사
}
}
static void postOrder(MyNode root) {
if (root != null) {
postOrder(root.left);
postOrder(root.right);
sb.append(root.data + " ");
}
}
}
class MyNode {
int data;
MyNode left;
MyNode right;
public MyNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
시간을 줄이기 위해 https://www.acmicpc.net/source/41515983 풀이를 참조하였다.
트리를 따로 만들 필요 없이 배열의 index를 활용해서 postOrder를 바로 출력하는 풀이다.
idx는 static 변수로 0번부터 검사하였고, rootIdx는 중위 순회에서의 index를 의미한다.
해당 rootIndex를 기준으로 왼쪽 값은 왼쪽 자식, 오른쪽 값은 오른쪽 자식이 되기 때문에 start와 end 범위에서 같은 과정을 반복하면 후위 순회를 쉽게 할 수 있다.
static void postOrder(int start, int end) {
if (start > end)
return;
int data = preOrder[idx++]; // 검색할 root
int rootIdx = -1;
for (int i = start; i <= end; i++) {
if (inOrder[i] == data) {
rootIdx = i;
break;
}
}
postOrder(start, rootIdx - 1);
postOrder(rootIdx + 1, end);
sb.append(data).append(" ");
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 1764 - 듣보잡 (0) | 2022.08.25 |
---|---|
[백준] 10815 - 숫자 카드 (자바/Java) (0) | 2022.08.25 |
[백준] 1991 - 트리 순회 (0) | 2022.08.24 |
[백준] 1182 - 부분수열의 합 (자바/Java) 재귀 부분집합 (0) | 2022.08.24 |
[백준] 11725 - 트리의 부모 찾기 (자바/Java) (1) | 2022.08.23 |