二叉树：判断是否为二叉搜索树

二叉搜索树

1、定义：

二叉搜索树（Binary Search Tree），（又：二叉查找树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

2、分析

根据定义，可以轻易的得出结论：

对于非叶子结点，只要保证结点左子树的最大值小于该结点的值，该结点的值小于结点右子树的最小值即可；
对于叶子结点，如果是父结点的左孩子，小于父结点；右孩子大于父结点即可

3、代码实现

3.1 递归实现

public static int preValue1 = Integer.MIN_VALUE;
public static boolean isBST(Node head) {
    if (head == null) {
        return true;
    }
    boolean isLeftBst = isBST(head.left);
    //如果左数不是搜索二叉树，直接返回 false
    if (!isLeftBst) {
        return false;
    }
    if (head.value <= preValue1) {
        return false;
    } else {
        preValue1 = head.value;
    }
    return isBST(head.right);
}

3.2 非递归、利用栈实现

思想与二叉树的非递归中序遍历类似，只是加了一个比较的步骤。

二叉树：二叉树的遍历 - 简书 (jianshu.com)

public static boolean isBST2(Node head) {
    if (head != null) {
        int preValue = Integer.MIN_VALUE;
        Stack<Node> s = new Stack();
        while (!s.empty() || head != null) {
            if (head != null) {
                s.push(head);
                head = head.left;
            } else {
                head = s.pop();
                if (head.value <= preValue) {
                    return false;
                } else {
                    preValue = head.value;
                }
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
    }
    return true;
}

3.3 递归，自定义类

每个结点都需要知道左子树是不是二叉搜索树，还需要知道左子树的最小值以及右子树的最大值，然后自己还要给自己的父结点返回以自己为首的树是不是二叉搜索树，以及自己的最大或最小值，所以我们可以自定义一个返回信息类。

//返回信息类
public static class ReturnData {
    public boolean isBST;//是否是二叉搜索树
    public int max;//最大值
    public int min;//最小值

    public ReturnData(boolean isBST, int max, int min) {
        this.isBST = isBST;
        this.max = max;
        this.min = min;
    }
}

具体判断过程：

public static ReturnData process(Node head) {
    if (head == null) {
        return null;
    }
    ReturnData leftData = process(head.left);
    ReturnData rightData = process(head.right);
    System.out.print(head.value + " ");
    int max = head.value;
    int min = head.value;
    if (leftData != null) {
        min = Math.min(min, leftData.min);
        max = Math.max(max, leftData.max);
    }
    if (rightData != null) {
        min = Math.min(min, rightData.min);
        max = Math.max(max, rightData.max);
    }
    //boolean isBST = true;
    //if (leftData != null && (!leftData.isBST || leftData.max >= head.value)) {
    //    isBST = false;
    //}
    //if (rightData != null && (!rightData.isBST || rightData.min <= head.value) {
    //    isBST = false;
    //}
    //与上面注释的代码等效
    boolean isBST = false;
    if (
            (leftData != null ? (leftData.isBST && leftData.max < head.value) : true)
            &&
            (rightData != null ? (rightData.isBST && rightData.min > head.value) : true)
        ) {
        isBST = true;
    }
    return new ReturnData(isBST, max, min);
}

主调用：

public static boolean isBST3(Node head) {
    return process(head).isBST;
}