Coding - Algo/Java
[백준] 5639번:이진 검색 트리(Java 자바)
jainn
2021. 12. 11. 23:51
728x90
문제
https://www.acmicpc.net/problem/5639
5639번: 이진 검색 트리
트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다
www.acmicpc.net
풀이 및 소스코드
https://girawhale.tistory.com/59
[백준] 5639번: 이진 검색 트리 - JAVA
🔗 문제 링크 BOJ 5639번: 이진 검색 트리 1️⃣ 트리 직접 그리기 📝 풀이 과정 전위 순회의 경우 처음 탐색한 값이 항상 root 이기 때문에 먼저 처음 값을 root로 설정해 주었다. 이후 반복문을 돌
girawhale.tistory.com
위 티스토리 참고해서 풀었다.
다시 한 번 더 풀어봐야겠다. !!!!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer> tree;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//StringTokenizer st;
tree = new ArrayList<Integer>();
while(true) {
String n = br.readLine();
if(n==null||n.equals("")) break;
// 더이상의 인풋이 존재하지 않으면 break
tree.add(Integer.parseInt(n));
}
postOrder(0, tree.size()-1);
}
public static void postOrder(int idx, int end) {
if(idx>end) return;
// 리스트 범위를 벗어나면 return
int mid = idx+1;
while(mid<=end && tree.get(mid)<tree.get(idx)) {
mid++;
}
postOrder(idx+1, mid-1);
postOrder(mid, end);
System.out.println(tree.get(idx));
}
}반응형