[BOJ_5639 | Tree] 이진 검색 트리

이진 검색 트리(Binary Search Tree) 문제는 트리의 순회 결과가 주어졌을 때

트리를 유일하게 결정할 수 있는지에 대해서 물어보는 문제였던 것 같다.

학교에서 배울 때는 어느 한 가지의 순회(중위 순회, 전위 순회, 후위 순회)결과를 가지고는

트리를 유일하게 결정할 수 없으며

중위 순회와 전위 순회

혹은

중위 순회와 후위 순회

의 결과가 주어졌을 때 트리를 유일하게 결정할 수 있다.

위 문제에서는 중위 순회 결과에 대해서는 고민할 필요가 없는데, 

이진 검색트리에서 중위 순회한 결과는 오름차순의 데이터이기 때문이다

따라서 중위 순회와 전위 순회의 결과를 가지고 트리를 유일하게 구성할 수 있었고

재귀 함수를 이용하여 노드 삽입과 후위 순회를 구현하여 문제를 해결하였다.

import java.util.*;
 
 
class Tree{
    class Node{
        private Node left, right;
        private int val;
        Node(int val){
            this.val = val;
        }
    }
    private Node root;
    public Node getRoot(){return root;}
    Tree(){root = null;}
    public Node insert(Node curNode, int val){
        if(curNode == null) return new Node(val);
        if(curNode.val > val) curNode.left = insert(curNode.left, val);
        else curNode.right = insert(curNode.right, val);
        return curNode;
    }
    public void postOrder(Node curNode){
        if(curNode == null) return;
        postOrder(curNode.left);
        postOrder(curNode.right);
        System.out.println(curNode.val);
    }
}
 
public class BOJ_5639 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        Tree tree = new Tree();
        Tree.Node root = tree.getRoot();
        int val;
        while(input.hasNextInt()){
            val = input.nextInt();
            root = tree.insert(root, val);
        }
        tree.postOrder(root);
    }
}