/**
 * 判断一个二叉树是否为搜索二叉树
 */

public class SearchBinaryTree {
    public static void main(String[] args) {
        BinaryTreeNode node1 = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node6 = new BinaryTreeNode(6);
        BinaryTreeNode node7 = new BinaryTreeNode(7);
        BinaryTreeNode node8 = new BinaryTreeNode(8);
        BinaryTreeNode node9 = new BinaryTreeNode(9);
        node4.left = node5;
        node2.left = node1;
        node2.right = node3;
        node4.right = node2;
        System.out.println(Recure(node4).b);

    }

    public static int preValue = Integer.MIN_VALUE;
    //方法1
    public static boolean SearchTree(BinaryTreeNode root){
        if (root == null){
            return true;
        }
        boolean b = SearchTree(root.left);
        if (!b){
            return false;
        }
        if (root.value < preValue){
            return false;
        }else {
            preValue = root.value;
        }
        return SearchTree(root.right);
    }

    //方法2
    public static class ReturnData {
        boolean b;
        int min;
        int max;
        public ReturnData(boolean b, int min, int max){
            this.b = b;
            this.min = min;
            this.max = max;
        }
    }

    public static ReturnData Recure(BinaryTreeNode root){
        if (root == null){
            return null;
        }
        ReturnData left = Recure(root.left);
        ReturnData right = Recure(root.right);

        int min = root.value;
        int max = root.value;
        if (left != null){
            max = Math.max(max, left.max);
        }
        if (right != null){
            min = Math.min(min, right.min);
        }

        boolean isBST = true;
        if (left != null && (left.max > root.value || !left.b)){
            isBST = false;
        }
        if (right != null && (right.min < root.value || !right.b)){
            isBST = false;
        }

        return new ReturnData(isBST, min, max);
    }
}