728x90
문제 풀이
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
public class Main {
static HashMap<Integer, Node> hm = new HashMap<>();
static StringBuilder sb = new StringBuilder();
static class Node {
private int val; // parant/root node value
private Node left, right; // child/sub left node, child right node
public Node( int val ) {
this.val = val;
}
public int getVal() {
return val;
}
public void setVal( int val ) {
this.val = val;
}
public Node getLeft() {
return left;
}
public void setLeft( Node left ) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight( Node right ) {
this.right = right;
}
}
public static void postOrder( Node root ) {
Node l = root.getLeft(), r = root.getRight();
if( l != null ) postOrder( hm.get( l.getVal() ) );
if( r != null ) postOrder( hm.get( r.getVal() ) );
sb.append( root.getVal() + "\n" );
}
// start, end, len, order
public static void createTree( int s, int e, int l, Integer o[] ) {
if( l <= 1 )
return;
int root, left, right, i;
int sl = -1, el = -1, sr = -1, er = -1; // start/end post-order left/right
int cl = 0, cr = 0; // calculate len left/right
root = o[s]; // 루트 구하기
for( i = s+1; i <= e; i++ ) // 서브 트리 구하기
if( root < o[i] )
break;
sl = l > 0 && root > o[s+1] ? s+1 : -1;
sr = l > 0 && i <= e && root < o[i] ? i : -1;
el = sl == -1 ? -1 : sr == -1 ? e : sr-1;
er = sr == -1 ? -1 : e;
cl = el-sl+1;
cr = er-sr+1;
left = sl == -1 ? -1 : o[sl];
right = sr == -1 ? -1 : o[sr];
if( left != -1 ) hm.get( root ).setLeft( hm.get( left ) );
if( right != -1 ) hm.get( root ).setRight( hm.get( right ) );
if( cl > 0 ) createTree( sl, el, cl, o );
if( cr > 0 ) createTree( sr, er, cr, o );
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<Integer> order = new ArrayList<>(); // pre-order
int n;
while( sc.hasNext() ) {
n = sc.nextInt();
order.add( n );
hm.put( n, new Node( n ) );
}
sc.close();
int l = order.size();
Integer o[] = (Integer[])order.toArray( new Integer[l] );
createTree( 0, l-1, l, o );
postOrder( hm.get( o[0] ) ); // root node
System.out.println( sb.toString() );
}
}
* 이진 탐색 트리( BST : Binary Search Tree )의 순회( traversal )
- 이진 탐색 트리의 특징
- 루트 노드를 기준으로, 좌측의 노드들은 모두 루트 노드 값보다 작고, 우측의 노드들은 모두 루트 노드 값보다 크다
- Node 클래스 작성
- field => 노드의 값, 왼쪽 자식 노드, 오른쪽 자식 노드
- method => 노드의 값을 파라미터로 받는 생성자, 각 field의 setter, getter
- postOrder( root ) 함수 작성
- post-order : left child -> right child -> root
- createTree() 함수 작성
- pre-order : 제일 앞 순서가 루트 노드 이다 => 루트 노드를 구함
- 이진 탐색 트리 : 루트 값보다 작은 값들은 왼쪽 서브 트리에, 루트 값보다 큰 값들은 오른쪽 서브 트리에 있다
=> 왼/오 서브 노드들의 각각의 개수를 구함
- 노드의 개수가 미리 주어지지 않으므로 입력값이 없을 때까지 입력을 받아야 하는데, Scanner로 입력을 받고, Scanner.hasNext() 함수를 이용하여 입력 받기를 반복함
- 또한 노드의 번호가 연속되지 않기 때문에 HashMap을 생성하여 key는 노드의 값, value는 노드가 되도록 한다
반응형
'코딩 문제 풀기 ( Algorithm problem solving ) > 백준 온라인 저지 ( BOJ )' 카테고리의 다른 글
[백준(Baekjoon)][자바(java)] 1717 : 집합의 표현 / 유니온 파인드 (0) | 2020.12.30 |
---|---|
[백준(Baekjoon)][자바(java)] 2957 : 이진 탐색 트리 / 트리를 사용한 집합과 맵 (0) | 2020.12.21 |
[백준(Baekjoon)][자바(java)] 2263 : 트리의 순회 / 트리 (0) | 2020.12.17 |
[백준(Baekjoon)][자바(java)] 1991 : 트리 순회 / 트리 (0) | 2020.12.17 |
[백준(Baekjoon)][자바(java)] 1967 : 트리의 지름 / 트리 (0) | 2020.12.17 |