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

문제

• 링크 : https://www.acmicpc.net/problem/5639
• 이진 검색 트리의 전위 순회한 결과를 통해서 후쉬 순회한 결과 출력하기

 

• 조건
  • 노드의 왼쪽 서브 트리는 노드보다 작다
  • 노드의 오른쪽 서브 트리는 노드보다 크다

 

• 입력
  • 이진 검색 트리의 전위 순회한 결과
  • 0 ≤ 노드의 키 값 ≤ 10^6
  • 노드의 키 값 : 정수
  • 노드의 수 ≤ 10,000
  • 중복된 노드의 키는 존재 X

 

• 출력
  • 이진 검색 트리의 후위 순회한 결과

•  

 

• 로직 1)
  • node를 이용해서 tree 구현하기
  • 입력값이 추가될 위치를 알기 위해서 stack 구현하기
    • stack는 Node 클래스 객체 저장
  • 입력값을 통해서 이진 검색 트리 구하기
    
    • 첫번째 값은 루트
    • 입력값이 stack의 마지막값보다 작은 경우
      • stack의 마지막의 왼쪽 노드에 추가하기
      • 입력값을 stack에 추가하기
    • 입력값이 stack의 마지막값보다 큰 경우
    • stack을 계속 pop하다가 가장 먼저 만나는 큰 값의 왼쪽 노드의 오른쪽 노드에 입력값 추가하기
  • 이진 검색 트리의 후위 순회 출력하기
    • DFS하기 위해서 재귀를 이용해서 구현

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

// 이진 검색 트리
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String num;

        // 루트 생성하기
        Node bst = new Node(Integer.valueOf(br.readLine())); // 이진 탐색 트리 구현체

        // 입력값 추가하는 위치를 알기위한 stack
        Stack<Node> stack = new Stack<>();
        stack.push(bst);

        // 입력이 있을때까지 반복을 통해서 이진 검색 트리 구현하기
        while((num = br.readLine()) != null) {
            bst.add(Integer.valueOf(num), stack); // 입력값을 트리에 추가하기
        }

        bst.postOrderPrint(bst); // 이진 탐색 트리의 후위순회 출력하기
    }

    public static class Node {
        private int value; // 노드의 값
        private Node LeftNode; // 왼쪽 노드 주소
        private Node RightNode; // 오른쪽 노드 주소

        public Node() {} // 생성자

        public Node(int value) { // value값을 지정하는 생성자
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public static void add(int num, Stack<Node> stack) { // 노드 추가하기(num은 추가한 value의 값)
            Node tmp = stack.peek();

            if(num < tmp.value && tmp.LeftNode == null) { // 입력값이 stack의 마지막값보다 작은 경우
                tmp.LeftNode = new Node(num);
                stack.push(tmp.LeftNode);
            } else { // 입력값이 stack의 마지막값보다 작은 경우
                while(num > (tmp = stack.peek()).value) {
                    stack.pop();
                    if(stack.isEmpty()) break;
                }

                if(stack.isEmpty()) {
                    tmp.RightNode = new Node(num);
                    stack.add(tmp.RightNode);
                }
                else if(tmp.LeftNode != null) tmp.LeftNode.RightNode = new Node(num);
                else tmp.RightNode = new Node(num);
            }
        }

        // 이진 탐색 트리의 후위 순회 출력하기
        public static void postOrderPrint(Node node) {

            if(node.LeftNode != null) postOrderPrint(node.LeftNode);
            if(node.RightNode != null) postOrderPrint(node.RightNode);
            System.out.println(node.value);
        }
    }
}

 

• 결과
  • 실패

 

• 로직 2)
  • node를 이용해서 tree 구현하기
  • 입력값을 통해서 이진 검색 트리 구하기
    
    • 첫번째 값은 루트
    • 재귀 이용하기
      • 루트보다 크면 오른쪽 노드 삽입하기, 작으면 왼쪽 노드 삽입하기
      • 만약 삽입하려는 위치에 노드가 있다면 
  • 이진 검색 트리의 후위 순회 출력하기
    • DFS하기 위해서 재귀를 이용해서 구현

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

// 이진 검색 트리
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String num;

        // 루트 생성하기
        Node bst = new Node(Integer.valueOf(br.readLine())); // 이진 탐색 트리 구현체

        // 입력이 있을때까지 반복을 통해서 이진 검색 트리 구현하기
        while((num = br.readLine()) != null) {
            bst.insert(bst, Integer.valueOf(num)); // 입력값을 트리에 추가하기
        }

        bst.postOrderPrint(bst); // 이진 탐색 트리의 후위순회 출력하기
    }

    public static class Node {
        private int value; // 노드의 값
        private Node LeftNode; // 왼쪽 노드 주소
        private Node RightNode; // 오른쪽 노드 주소

        public Node() {} // 생성자

        public Node(int value) { // value값을 지정하는 생성자
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public static void insert(Node node, int num) { // 노드 추가하기(num은 추가한 value의 값)
            if(num < node.value) {
                if(node.LeftNode == null) node.LeftNode = new Node(num);
                else insert(node.LeftNode, num);
            } else {
                if(node.RightNode == null) node.RightNode = new Node(num);
                else insert(node.RightNode, num);
            }
        }

        // 이진 탐색 트리의 후위 순회 출력하기
        public static void postOrderPrint(Node node) {
            if(node.LeftNode != null) postOrderPrint(node.LeftNode);
            if(node.RightNode != null) postOrderPrint(node.RightNode);
            System.out.println(node.value);
        }
    }
}

 

• 결과
  • 성공

 

• 회고
  • stack을 이용해서 문제를 해결하려고 하니 신경써야할 경우의 수가 늘어나는데 전부 신경쓰지 못해서 문제를 해결하지못함
  • 재귀를 사용함으로써 문제를 쉽게 성공 가능