트리 이용한 간단한 응용문제

문제 1

// Practice1
// 주어진 이진 탐색 트리에서 N 번째로 작은 수 구하기

// 입력 트리: 3, 1, 4, null, 2
// N: 1
// 결과: 1

// 입력 트리: 5, 3, 6, 2, 4, null, null, 1
// N: 3
// 결과: 3

public class Practice1 {
    public static void solution(Integer[] data, int n) {
        BinarySearchTree bst = new BinarySearchTree();
        int cnt = 0;

        for(int i = 0; i < data.length; i++){
            if(data[i] == null){
                continue;
            }
            bst.addNode(data[i]);
        }

        ArrayList<Integer> list  = new ArrayList();
        inOrder(bst.head, list);
        System.out.println(list.get(n-1));

    }

    public static void inOrder(Node node, ArrayList list){
        if(node == null){
            return;
        }
        inOrder(node.left, list);
        list.add(node.key);
        inOrder(node.right, list);
    }

    public static void main(String[] args) {
        // Test code
        Integer[] data = {3, 1, 4, null, 2};
        int n = 1;
        solution(data, n);

        data = new Integer[]{5, 3, 6, 2, 4, null, null, 1};
        n = 3;
        solution(data, n);
    }
}

문제 2

// Practice2
// 주어진 BST 에서 노드 간의 차이값 중 최소 값을 구하세요.

// 입력 트리: 4, 2, 6, 1, 3
// 출력: 1

// 입력 트리: 5, 1, 48, null, null, 12, 51
// 출력: 3

public class Practice2 {

    public static void solution(Integer[] data) {
        BinarySearchTree bst = new BinarySearchTree(data[0]);

        for(int i = 1; i < data.length; i++){
            if(data[i] == null){
                continue;
            }
            bst.addNode(data[i]);
        }

        ArrayList<Integer> list = new ArrayList<>();
        levelOrder(bst.head, list);

//        int min = list.stream().min((x1, x2) -> x1 > x2 ? 1: -1).get();
        int min = Collections.min(list);
        System.out.println(min);

    }

    public static void levelOrder(Node node, ArrayList<Integer> list){
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);

        while(!queue.isEmpty()){
            Node cur = queue.poll();

            if(cur.left != null){
                queue.offer(cur.left);
                list.add(Math.abs(cur.key - cur.left.key));
            }

            if(cur.right != null){
                queue.offer(cur.right);
                list.add(Math.abs(cur.key - cur.right.key));
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        Integer[] data = {3, 1, 4, null, 2};
        solution(data);

        data = new Integer[]{5, 1, 48, null, null, 12, 51};
        solution(data);
    }
}

문제3

// Practice3
// 주어진 BST 에서 두 노드의 합이 target 값이 되는 경우가 있는지 확인하세요.
// 있으면 true, 없으면 false 반환

// 입력 트리: 5, 3, 6, 2, 4, null, 7
// 결과: true

// 입력 트리: 5,3,6,2,4,null,7
// 결과: false

public class Practice3 {
    public static void solution(Integer[] data, int target) {
        BinarySearchTree bst = new BinarySearchTree(data[0]);

        for(int i = 1; i < data.length; i++){
            if(data[i] == null){
                continue;
            }
            bst.addNode(data[i]);
        }

        HashSet<Integer> set = new HashSet<>();
        boolean result = search(bst.head, set, target);
        System.out.println(result);
    }

    public static boolean search(Node node, HashSet<Integer> set, int target){
        if(node == null){
            return false;
        }

        if(set.contains(target - node.key)){
            return true;
        }

        set.add(node.key); // 방문 하였음

        if(search(node.left, set, target)){
            return true;
        }

        if(search(node.right, set , target)){
            return true;
        }

        return false;
    }

    public static void main(String[] args) {
        Integer[] data = {5, 3, 6, 2, 4, null, 7};
        int target = 9;
        solution(data, target);

        data = new Integer[]{5,3,6,2,4,null,7};
        target = 28;
        solution(data, target);
    }
}