[BOJ 5639] 이진 검색 트리알고리즘/트리2023. 6. 26. 15:58
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/5639
문제 풀이
- 정적 클래스를 정의하여 주어진 입력값을 이진 검색 트리(전위 순회) 방식으로 정의
- 이전에 풀었던 트리 순회와 동일하게 재귀 함수 사용하여 후위 순회 구할 수 있도록 함
- 노드의 최대 개수는 10^4 이고, 각 노드 별로 최대 2번 재귀를 호출할 때 O(2 * 10^4) 시간 복잡도 소요
참고
https://dev-ljw1126.tistory.com/248
제출 코드
import java.util.*;
import java.io.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static Node ROOT;
static class Node {
int value;
Node left;
Node right;
public Node(int _value) {
this.value = _value;
}
public void insert(int _value) {
if(this.value > _value) {
if(this.left == null) this.left = new Node(_value);
else this.left.insert(_value);
} else {
if(this.right == null) this.right = new Node(_value);
else this.right.insert(_value);
}
}
}
static void input() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
String input = br.readLine();
if(input == null || "".equals(input)) break;
int value = Integer.parseInt(input);
if(ROOT == null) ROOT = new Node(value);
else ROOT.insert(value);
}
br.close();
}
// 후위 순회 - 왼쪽 오른쪽 부모
static void postorder(Node node) {
if(node == null) return;
postorder(node.left);
postorder(node.right);
sb.append(node.value).append("\n");
}
static void pro() {
postorder(ROOT);
System.out.println(sb);
}
public static void main(String[] args) throws Exception {
input();
pro();
}
}
반응형
'알고리즘 > 트리' 카테고리의 다른 글
[BOJ 9489] 사촌 (Java, 트리) (0) | 2023.06.26 |
---|---|
[BOJ 3584] 가장 가까운 공통 조상 (Java, DFS, LCA) (0) | 2023.06.26 |
[BOJ 20364] 부동산 다툼 (Java, Tree) (0) | 2023.06.26 |
[BOJ 15900] 나무 탈출 (Java, DFS, Tree) (0) | 2023.06.26 |
[BOJ 1991] 트리 순회 (0) | 2023.06.26 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!