BOJ_1708_이진검색트리_JAVA
문제 : 이진검색트리
링크 : BOJ_1708_이진검색트리
접근 방식
이진 검색 트리의 조건을 만족하는 트리의 전위 순회 결과가 주어졌을 때, 이 트리의 후위 순회 결과를 구하면 되는 문제이다.
이진 검색 트리의 조건은 다음과 같다.
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class BOJ_1708_이진검색트리 {
static class Node {
int v;
Node left;
Node right;
public Node(int v) {
this.v = v;
}
public Node(int v, Node left, Node right) {
this.v = v;
this.left = left;
this.right = right;
}
void insert(int v) {
// 현재 정점보다 더 작은 수일 경우
if (this.v > v) {
// 왼쪽 자식에 노드가 없다면
if (this.left == null) {
// 자식으로 노드 추가
this.left = new Node(v);
} else {
// 노드가 있다면 그 자식의 insert 메서드 호출
this.left.insert(v);
}
// 현재 정점보다 더 큰 수일 경우
} else {
// 오른쪽 자식에 노드가 없다면
if (this.right == null) {
// 자식으로 노드 추가
this.right = new Node(v);
} else {
// 노드가 있다면 오른쪽 자식 노드에서 insert 메서드 호출
this.right.insert(v);
}
}
}
}
public static void main(String[] args) {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Node root = null;
try {
root = new Node(Integer.parseInt(in.readLine()));
while (true) {
int node = Integer.parseInt(in.readLine());
root.insert(node);
}
} catch (Exception e) {
}
post(root);
}
// 후위순회 왼 오 중
static void post(Node node) {
Node L = node.left;
Node R = node.right;
if (L != null) {
post(node.left);
}
if (R != null) {
post(node.right);
}
System.out.println((node.v));
}
}
이진검색트리의 전위순회 결과를 읽어와서 트리를 만들고, 만들어진 트리를 후위순회하여 출력했다.