题目地址：验证二叉树搜索

解题思路一

本文解题思路来自左程云老师算法课新手班第七节

二叉树的左节点小于根节点，右节点大于根节点，只需要判断，中序遍历是否严格递增即可。

比如示例一，其中序遍历为123，严格递增，也就是搜索二叉树

示例二：

其中序遍历为1 5 3 4 6，不是严格递增，所以不是搜索二叉树

中序遍历如何获得，之前说过，如有遗忘，请移步。

那么现在有一个二叉树中序遍历的链表或者数组，此处使用链表最好。因为并不清楚有多少节点，数组的扩容相对耗时

如何去判断其是否为严格递增呢？

因为数据量并不大，最多只有10⁴的节点。所以可以遍历判断，两两比较。

其中较为关键是，获取当前节点的值使用get方法，循环中size要减一，否则会超范围，还有必须加等号不然会出现这种情况了。

        int size = list.size();
        for (int i = 0; i <size-1 ; i++) {
            if (list.get(i)>=list.get(i+1)) {
                return false;
            }
        }

解题思路一 完整代码

    List<Integer> list = new LinkedList<>();
    public  void getList(TreeNode root){
        if (root == null) {
            return;
        }
        getList(root.left);
        list.add(root.val);
        getList(root.right);
    }
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        getList(root);
        int size = list.size();
        for (int i = 0; i <size-1 ; i++) {
            if (list.get(i)>=list.get(i+1)) {
                return false;
            }
        }
        return true;
    }

解题思路二

本文解题思路来自左程云老师算法课新手班第七节

使用递归的思想，一个节点的是否搜索，取决于，它的左树是否搜索，它的右树是否搜索，已经这个节点是否满足大于左树最大，小于右树最小

那么递归是需要返回一致的信息，那么就创建一个类用于返回，类里面包括是boolean的是否搜索，

两个int，一个最大值，一个最小值

    public class info {
        boolean isBST;
        int max;
        int min;

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

接下来就是递归，如果这个节点是空，那么一定是搜索的，最大最小值不管赋予啥都有反例。

所以直接全部返回空

if (root == null) {
    return null;
}

接下来递归去抓住左右的信息

info leftinfo = process(root.left);
info rightinfo = process(root.right);

然后加工这个节点的信息，首先是min和max，先假设该节点就是最大或者最小，如果左右节点不为空，那么就会有该节点的左右信息，去和里面的最大最小进行一次选择。确定这个节点的最大和最小

        int max = root.val;
        int min = root.val;
        if (leftinfo != null) {
            max = Math.max(leftinfo.max, max);
            min = Math.min(leftinfo.min, min);
        }
        if (rightinfo != null) {
            max = Math.max(rightinfo.max, max);
            min = Math.min(rightinfo.min, min);
        }

接下来是IsBST的加工，首先假设它为true，这个节点为true的条件是左树为true，右树为true，同时左树最大小于节点值，节点值小于右树最小。

那么，很好理解，代码如下

        boolean IsBST = true;
        if (leftinfo != null && !leftinfo.isBST) {
            IsBST = false;
        }
        if (rightinfo != null && !rightinfo.isBST) {
            IsBST = false;
        }
        boolean leftMaxLessX = leftinfo == null ? true : leftinfo.max < root.val;
        boolean rightMinMoreX = rightinfo == null ? true : (rightinfo.min > root.val);
        if (!(leftMaxLessX && rightMinMoreX)) {
            IsBST = false;
        }

解题思路二 完整代码

    public class info {
        boolean isBST;
        int max;
        int min;

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

    public info process(TreeNode root) {
        if (root == null) {
            return null;
        }
        info leftinfo = process(root.left);
        info rightinfo = process(root.right);

        int max = root.val;
        int min = root.val;
        if (leftinfo != null) {
            max = Math.max(leftinfo.max, max);
            min = Math.min(leftinfo.min, min);
        }
        if (rightinfo != null) {
            max = Math.max(rightinfo.max, max);
            min = Math.min(rightinfo.min, min);
        }
        boolean IsBST = true;
        if (leftinfo != null && !leftinfo.isBST) {
            IsBST = false;
        }
        if (rightinfo != null && !rightinfo.isBST) {
            IsBST = false;
        }
        boolean leftMaxLessX = leftinfo == null ? true : leftinfo.max < root.val;
        boolean rightMinMoreX = rightinfo == null ? true : (rightinfo.min > root.val);
        if (!(leftMaxLessX && rightMinMoreX)) {
            IsBST = false;
        }
        return new info(IsBST, max, min);
    }

    public boolean isValidBST(TreeNode root) {

        return process(root).isBST;
    }