5639번 이진 검색 트리

골드4 - 이진 검색 트리

소스 코드

문제 링크

import java.io.*;

public class Main {
    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            // 전위순회를 하기 때문에 입력의 첫 값은 항상 Root Node가 된다.
            Node root = new Node(Integer.parseInt(br.readLine()));
            String input;
            while (true) {
                input = br.readLine();
                if (input == null || input.isBlank()) {
                    break;
                }

                Node node = new Node(Integer.parseInt(input));
                root.insert(node);
            }

            //재귀로 후위순회를 한다.
            postOrder(root);

            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

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

        public Node(int value) {
            this.value = value;
            left = right = null;
        }

        public void insert(Node node) {
            if (value > node.value) {
                insertLeft(node);
            } else if (value < node.value) {
                insertRight(node);
            }
        }

        private void insertLeft(Node node) {
            if (left == null) {
                this.left = node;
            } else {
                left.insert(node);
            }

        }

        private void insertRight(Node node) {
            if (right == null) {
                this.right = node;
            } else {
                right.insert(node);
            }
        }
    }

    static StringBuilder sb = new StringBuilder();

    private static void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);

        sb.append(node.value).append('\n');
    }
}

---

풀이 방법

이진 트리의 순회 방법과 어떻게 트리가 만들어지는지 이해하고 있으면 아주 쉽게 풀 수 있는 문제다.

트리를 만들기 위해 Node 클래스를 생성하고 insert() 메서드를 통해서 값을 비교 후 왼쪽과 오른쪽 위치를 결정한다.

모든 노드를 생성해서 트리를 만들고 나면 root를 시작점으로 잡고 postOrder() 메서드를 실행.

재귀를 사용해서 왼쪽을 먼저 탐색하고 오른쪽을 탐색, 그 이후에 현재 위치의 값을 출력하면 끝!

기저 조건으로 node == null 을 설정해서 postOrder(node.left) / postOrder(node.right) 가 null인지 체크.

이렇게만 하면 재귀를 통해 왼쪽 - 오른쪽 - 루트 를 지키면서 트리를 탐색할 수 있다!!

---

어려웠던(?) 점

문제에 입력이 언제 끝나는지 주어지지 않아서

뭐야.. 그럼 입력이 끝나는건 어떻게 알아? 그냥 내 맘대로 null이나 ""(빈 값)이 넘어오면 입력이 끝난거라고 해야해..?

왜 끝나는 조건이 없어!!! 하고 엄청 생각하면서 문제를 읽고 또 읽었다.

입력의 끝을 어떻게 해야할 지 몰라서 풀이에서 입력의 끝을 어떻게 처리하는 지만 확인하자 하고 찾아보니... 내가 생각한 대로 풀었넹???

조건이 없으면 그냥 내 맘대로 설정하면 되는건지... 다른 문제는 내 맘대로 풀면 안되는데 입력 받는 거라서 괜찮은건가..???

입력에 대한 부분은 조금 아리까리 하긴 했지만 이진 탐색 트리를 만드는 부분은 알고리즘 공부를 할 때 몇 번 해봤던 거라서 조금 쉽게 작성할 수 있었다!! 기부니 조와~~