백준 5639 - 이진 검색 트리

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

5639번: 이진 검색 트리

 

Note

이 문제를 풀기위한  설명은 이진탐색트리(Binary Search Tree)  POST를 참고하면 되는데 preorder ▶이진탐색트리(BST) 생성 ▶ postorder 순회하여 출력하면 끝.

문제를 푸는 핵심은 전위순회를 가지고 어떻게 이진탐색트리를 만드냐 인데 preorder -> 이진탐색트리 생성 방법은 아래와 같다.

예를들어 preorder sequence 가 { 10, 5, 1, 7, 40, 50 } 가 되어 있다면

1.  preorder 순서 중 첫번째 키는 항상 이진트리의 루트(root) 노드이기 때문에 루트노드를 생성 한다. (ex. 10 이 루트노드가 된다.)
2. 그 다음에 루트 노드 보다 큰 키값을 가진 첫 번째 요소를의 인덱스 i 를 찾는다. ( ex. 여기서는 40 이 루트노드 10보다 큰 값을 가진 것중 가장 첫번째 요소이다. )
3. 루트노드를 제외한 i 이전 까지의 키들은 왼쪽 서브트리(left subtree)가 되고 ( ex. left subtree ∈ { 5, 1, 7 } )
4. i 를 포함하여 i 이후의 모든 키들은 오른쪽 서브트리(right subtree)가 된다.  ( ex. right subtree ∈  {40, 50} )
5. 1-4번을 재귀적으로 반복한다.   

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.function.Consumer;
 
 
public class Main {
    // Key 값은 비교 가능해야하니 Comparable 를 상속한 클래스이어야 한다.
    public static class BinarySearchTree {
 
        public Node root ;  // 이진탐색트리의 루트 노드
 
        public class Node {
            public int key    ; // 노드의 키값이고 이거에 의해 정렬되어 질 것이다.
            public Node left  ; // 왼쪽 서브트리 노드,
            public Node right ; // 오른쪽 서브트리
 
            public Node(int key) {
                this.key = key;
            }
        }
 
 
        public void postorderTraversal(Node node, Consumer<Node> consumer) {
            if(node == null)
                return;
 
            // left -> right -> root
            postorderTraversal(node.left, consumer);
            postorderTraversal(node.right, consumer);
            if(consumer != null) consumer.accept(node);
        }
 
 
        public static BinarySearchTree newBSTFromPreOrder(int[] key) {
            BinarySearchTree bst = new BinarySearchTree();
            bst.root = bst.buildNodeFromPreorder(key, 0, key.length-1);
            return bst;
        }
 
        private Node buildNodeFromPreorder(int[] preorder, int start, int end) {
            // base case
            if (start > end) {
                return null;
            }
 
            Node node = new Node(preorder[start]);
 
            int i = start;
            while(i <= end) {
                if (preorder[i] > node.key) {
                    break;
                }
                i++;
            }
 
            node.left = buildNodeFromPreorder(preorder, start + 1, i - 1);
            node.right = buildNodeFromPreorder(preorder, i, end);
 
            return node;
        }
    }
 
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> list = new ArrayList<>();
 
        while(true) {
            String input = bf.readLine();
            if(input == null || input.isEmpty())
                break;
            list.add(Integer.parseInt(input));
 
        }
 
        int[] inputs = list.stream().mapToInt(i -> i.intValue()).toArray();
 
        BinarySearchTree bst = BinarySearchTree.newBSTFromPreOrder(inputs);
        bst.postorderTraversal(bst.root, (node) -> System.out.println(node.key));
    }
 
}