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

백준 5639번 문제 - 이진 검색 트리

5639번: 이진 검색 트리

---

문제 분석

• 이진 검색 트리가 전위 순회 (루트 - 왼쪽 - 오른쪽) 했을 때 결과를 입력
• 해당 이진 검색 트리를 후위 순회 (왼쪽 - 오른쪽 - 루트) 했을 때 결과를 출력

---

해결 키 포인트

 

• 전위 순회 입력을 통해 이진 검색 트리를 생성
  • 처음에 이전 루트를 기억해 해당 루트와 비교하여 트리를 생성하는 방법 사용
    1. 이전 루트 > 해당 루트 :  해당 루트를 이전 루트의 left로 설정
    2. 이전 루트 < 해당 루트 : 이전 루트의 부모 루트가 해당 루트보다 작을 때까지 반복하여 부모 루트를 찾고 right로 설정
  • 위 방식에 문제가 있음 → 그냥 최상위 루트부터 확인하면서 해당 루트 위치 찾는 식으로 변경 (확인하는 방법은 재귀함수로)
• 출력도 재귀함수로 제작하면 더 쉽다

---

코드

import java.io.*;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 최상위 루트 제작 및 설정
        Node firstNode = new Node(Integer.parseInt(br.readLine()));

        // 가장 최신 노드
        Node currentNode = firstNode;

        // 남은 전위 순회 값 입력
        String newInput = "";
        while((newInput = br.readLine()) != null && !newInput.isEmpty()) {
            Node newNode = new Node(Integer.parseInt(newInput));

            inputFrontCheck(firstNode, newNode);
        }

        // 후위순회 출력
        printBackCheck(firstNode);
        bw.flush();
        bw.close();
    }

    public static void inputFrontCheck(Node node, Node newNode) {
        // 현재 노드보다 새로운 노드 값이 작을 경우
        if(node.root > newNode.root) {
            // 왼쪽 노드가 없을 경우, 왼쪽 노드로 설정
            if(node.left == null)
                node.left = newNode;
            // 아닐 경우, 더 깊게 들어가기
            else
                inputFrontCheck(node.left, newNode);
        }
        // 현재 노드보다 새로운 노드 값이 클 경우
        else {
            // 오른쪽 노드가 없을 경우, 오른쪽 노드로 설정
            if(node.right == null)
                node.right = newNode;
            // 아닐 경우, 더 깊게 들어가기
            else
                inputFrontCheck(node.right, newNode);
        }
    }

    public static int printBackCheck(Node node) throws IOException {
        if(node == null) {
            return -1;
        }
        printBackCheck(node.left);
        printBackCheck(node.right);
        bw.write(node.root + "\n");

        return node.root;
    }

    public static class Node {
        public int root;
        public Node left = null;
        public Node right = null;

        public Node(int root) {
            this.root = root;
        }
    }
}