문제
이진탐색트리(자식 노드의 규칙,
현재 노드의 좌측 자식 노드는 현재 노드 보다 낮다,
현재 노드의 우측 자식 노드는 현재 노드 보다 높다) 가 전위순회(현재 노드, 좌측 노드, 우측 노드 순)로 입력 된다.
이를 후위순회하여 출력하는 문제이다.
내 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static class Node {
int num;
Node left;
Node right;
public Node(int num) {
this.num = num;
}
public void insert(int n) {
if (n < this.num) {
if (this.left == null) {
this.left = new Node(n);
} else this.left.insert(n);
} else {
if (this.right == null) {
this.right = new Node(n);
} else this.right.insert(n);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Node root = new Node(Integer.parseInt(br.readLine()));
String input;
while (true) {
input = br.readLine();
if (input == null)
break;
root.insert(Integer.parseInt(input));
}
postOrder(root);
}
static void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.num);
}
}
리뷰
- class Node
- 기본 노드 클래스를 만들어 key값인 num과 left, right를 활용한다.
- Method insert
- 노드 클래스를 활용해 입력 받는 값을 조건에 맞춰 tree를 만들어 낸다.
- 입력 방법
- BufferdReader를 이용해 첫 root 값을 미리 생성
- Node root = new Node(Integer.parseInt(br.readLine()));
- while 문을 돌며 입력 값이 없을 때 까지 값을 넣는다.
- 문제에서 노드의 수가 절대값으로 정해져있지 않기 때문에 while문을 활용한다.
- break 조건, if (input == null) 을 활용해 입력 값이 없을 때 까지 받아낸다.
- input.isEmpty()를 활용했을 경우 런타임 익셉션을 경험했다.
- BufferedReader의 readLine 메서드는 읽을 값이 없을 때 null을 반환한다. 때문에 isMepty()를 활용할 경우 null 값은 값이 비어있는 상태가 아니기 때문에 런타임 익셉션이 발생한다.
- BufferdReader를 이용해 첫 root 값을 미리 생성
- 생성 된 root를 최종적으로 postOrder 메서드를 이용해 출력해 낸다.
- Method postOrder(좌측노드, 우측 노드, 현재 노드 순)
- 좌측, 우측, 현재 노드 순으로 재귀적으로 출력해 낸다.
- 재귀함수인 이유로 return 조건 node == null을 꼭 넣어줘야한다.
- 좌측, 우측, 현재 노드 순으로 재귀적으로 출력해 낸다.
'연습문제 > 백준' 카테고리의 다른 글
| [백준_java] 적록색약(10026번) // dfs (2) | 2023.12.07 |
|---|---|
| [백준_java] 영수증(25304번) (0) | 2023.11.26 |
| [백준_java] 곱셈 (2588번) (1) | 2023.11.25 |
| [백준_java] 부녀회장이 될테야 (2775번) // dp (1) | 2023.11.23 |
| [백준_java] 설탕 배달 (2839번) // 그리디 알고리즘 // dp (0) | 2023.11.19 |
