문제 // 자료구조 // 트리(Tree) // BST검증 // toJava

/**
 *
 * [BST 검증]
 *  주어진 이진 트리가 이진탐색트리인지 확인하는 함수
 *
 * [풀이]
 *  => 트리에 중복이 있나요 ?
 *  => 주어진 노드를 받았을때 재귀로 계속 검증
 *  => 재귀로 검증할때 최상위에서부터 검사해야함
 *  => * 위에서 부터 타고 내려왔다면 노드마다 범위가 있음
 *
 * [해법]
 *  => 01. 중위순회
 *  => 02. left <= current < right
 *  => 전체크기를 알고 있는가 ?
 *      => 알고있다면 배열
 *      => 모른다면 리스트
 * */
public class Q05 {

    /* Main */
    public static void main(String[] args) {

        // @Test
        Node rootA = new Node(1);
        rootA.left = new Node(2);
        rootA.right = new Node(3);
        rootA.left.left = new Node(4);
        rootA.left.right = new Node(5);
        rootA.right.left = new Node(6);
        rootA.right.right = new Node(7);

        // @Test
        Node rootB = new Node(4);
        rootB.left = new Node(2);
        rootB.right = new Node(6);
        rootB.left.left = new Node(1);
        rootB.left.right = new Node(3);
        rootB.right.left = new Node(5);
        rootB.right.right = new Node(7);

        // == 범위순회테스트 ==
        System.out.println(checkBSTA(rootA, -1, Integer.MAX_VALUE));
        System.out.println(checkBSTA(rootB, -1, Integer.MAX_VALUE));

        // == 중위순회테스트 (index를 객체를 가지고 처리할 수도 있음) ==
        System.out.println(checkBSTB(rootA));
        System.out.println(checkBSTB(rootB));
    }

    /* Filed */
    static int index = 0;

    /* Node */
    static class Node {
        Node left;
        Node right;
        int data;
        int size;
        public Node(int data) {
            this.data = data;
        }
    }

    /* checkBST - 범위를 가지고 재귀 */
    public static boolean checkBSTA(Node root, int start, int end) {
        // == 최상위노드를 비교하지 못함 ==

        boolean checkLeft = true;
        boolean checkRight = true;
        if(root.left != null) {
            if(start < root.left.data && root.left.data < root.data) {
                checkLeft = checkBSTA(root.left, start, root.data);
            } else {
                return false;
            }
        }
        if(root.right != null) {
            if(root.data < root.right.data && root.right.data < end) {
                checkRight = checkBSTA(root.right, root.data, end);
            } else {
                return false;
            }
        }
        if(checkLeft && checkRight) return true;
        else return false;
    }

    /* checkBSTB */
    public static boolean checkBSTB(Node root) {
        int[] array = new int[root.size];
        inorder(root, array);
        for (int i = 0; i < array.length; i++) {
            if(array[i] <= array[i-1]) {
                index = 0;
                return false;
            }
        }
        index = 0;
        return true;
    }

    /* inorder - 중위순회 In-order Traversal */
    public static void inorder( Node root, int[] array) {
        if( root == null ) return;
        inorder( root.left, array );    // left
        array[index++] = root.data;     // middle
        inorder( root.right, array );   // right
    }
}