[백준] 5639번: 이진 검색 트리 - JAVA

🔗 문제 링크

BOJ 5639번: 이진 검색 트리

1️⃣ 트리 직접 그리기

📝 풀이 과정

전위 순회의 경우 처음 탐색한 값이 항상 root이기 때문에 먼저 처음 값을 root로 설정해 주었다.

이후 반복문을 돌며 Node에 insert함수를 구현해 현재 노드의 값보다 작으면 왼쪽 자식, 크면 오른쪽 자식으로 넘어가 null일 경우 해당 노드를 생성해주고 아니라면 재귀적으로 다시 탐색하는 방식으로 구현해주었다.

 

트리가 모두 완성되면 후위 순회 함수를 구현해 왼쪽 자식, 오른쪽 자식, 현재 노드 순으로 탐색해 출력해 주었다.

 

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static class Node {
        int num;
        Node left, right;

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

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

        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 || input.equals(""))
                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);
    }
}

 

📊 제출 결과

 

---

 

2️⃣ 배열로 풀어보기

📝 풀이 과정

문제를 풀고나서 다른 사람이 작성한 코드를 보며 직접 클래스로 구현했다면 절대 불가능한 코드 길이가 존재해 다른 풀이를 알아 보았다.

 

 

BST(이진 검색 트리)의 특징인데 왼쪽은 무조건 자신의 크기보다 작은 노드들로만 이루어져있고, 오른쪽은 큰 노드들로만 구성되어 있다.

 

 

이를 보게 되면 전위 우선 탐색시 제일 앞은 부모 노드로 하고 차례대로 보다가 부모보다 큰 노드를 발견하게 되면 해당 노드부터 오른쪽 자식 노드라는 것을 알게 된다!

 

 

이를 통해 시작 노드의 위치와 종료 노드의 위치를 재귀적으로 넘겨주면서 후위 탐색의 결과를 출력 해줄 수 있다.

 

💻 코드

import java.util.Scanner;

public class Main {
    static int[] tree = new int[10001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int idx = 0;
        while (sc.hasNext())
            tree[idx++] = sc.nextInt();

        postOrder(0, idx - 1);

    }

    static void postOrder(int n, int end) {
        if (n > end)
            return;

        int mid = n + 1;
        while (mid <= end && tree[mid] < tree[n])
            mid++;

        postOrder(n + 1, mid - 1);
        postOrder(mid, end);
        System.out.println(tree[n]);
    }
}

 

📊 제출 결과