[백준 5639] 이진 검색 트리(Java)

문제 링크 : https://www.acmicpc.net/problem/5639

이 문제는 트리를 구현하는 구현 문제입니다.

이진 검색 트리를 더 효과적으로 탐색하기 위해 Node 클래스를 생성하여 트리를 구현하였습니다. 각 노드의 왼쪽 및 오른쪽 자리를 할당한 후 루트 노드에 새로운 노드를 추가합니다. 이 때 현재 왼쪽 또는 오른쪽 자리가 비어 있다면 그 노드를 그대로 추가하고, 자리가 차있다면 그 노드의 값을 기준으로 왼쪽 또는 오른쪽에 값을 추가할지를 재귀함수로 탐색합니다.

출력 역시 재귀함수로 진행합니다. 후위 순회의 경우 왼쪽 노드와 오른쪽 노드를 재귀함수로 탐색한 이후 출력을 진행합니다. 이래야 리프 노드에 도착했을 때 출력문이 출력되어 후위 순회가 진행됩니다. 마찬가지로 전위 순회의 경우 탐색 이전에 출력을 하여 루트 노드에서부터 노드를 출력하는 방식으로 진행합니다.

여기서 주의할 점은 자바 버전입니다. 현재 IDE의 경우 17을 사용하고 있는데 문제 입력 특성상 입력값이 null일 경우를 감지해야 반복문을 무사히 종료할 수 있습니다. 하지만 17 버전에서는 입력받을 때까지 대기하는 현상이 발생하여 정상적으로 실행되지 않습니다. 반면 백준에서 제공하는 11 버전의 경우 입력값을 null로 받을 수 있어 이와 같은 풀이가 가능합니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Node root = new Node(Integer.parseInt(br.readLine()));

        while(true){
            String str = br.readLine();

            // Java 17의 경우 str값을 인식을 못해서 아래 구문으로 넘어가지 못함
            if(str == null || str.equals("")) break;

            int val = Integer.parseInt(str);
            root.insert(val);
        }

        postOrder(root);
    }

    static void postOrder(Node curr){
        if(curr == null) return;

        postOrder(curr.left);
        postOrder(curr.right);
        System.out.println(curr.val);
    }

    static class Node{
        int val;
        Node left, right;

        Node(int val){
            this.val = val;
        }

        Node(int val, Node left, Node right){
            this.val = val;
            this.left = left;
            this.right = right;
        }

        void insert(int n){
            if(n < this.val){
                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);
            }
        }
    }
}