LeetCode 98.验证二叉搜索树

1.题目：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3] 输出：true

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/validate-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.代码：

方法一：

思路

要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;//注意这里是返回true
        List<Integer> result = new ArrayList<>();
    method(root,result);
        
    for(int i=0;i<result.size()-1;i++){//判断集合是不是递增的，循环的范围也要注意
       if(result.get(i+1)<=result.get(i)){//注意这里是可以取等号的
           return false;
       }
    }
    return true;

    }
    public void method(TreeNode root, List<Integer> result){//递归中序遍历还是另外写一个方法吧，无返回值的方法
        if(root==null) return ;//注意这里只需要结束方法即可，不用返回值，方法本来就是不要返回值的
         method(root.left,result);//直接先左再右就行
         result.add(root.val);
        method(root.right,result);
    }
}

2.方法二：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 //一边遍历一遍判断是否是递增的
class Solution {
    long min = Long.MIN_VALUE;//注意不要放到方法里面，不然每次递归都会重新给一个最小值！！！
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        boolean left = isValidBST(root.left);//左
        if(root.val>min){//中
            min=root.val;//只要遍历到的后一个结点比前一个大，就重新给min赋值
        }else {
            return false;//否则就直接返回false
        }
        boolean right = isValidBST(root.right);//右
        return left && right;

    }
}

方法三：指针

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
     TreeNode pre = null;//定义一个指针，先指向null，注意也是不能放在方法里面，不然的话每次递归都会弄到
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        boolean left = isValidBST(root.left);//左
        if(pre!=null && pre.val>=root.val){//中，注意这里的条件，既要不为null，而且是大于等于
            return false;
        } else{
            pre=root;//这里的是移动指针，下一层递归？root也是会自己移动的
        }
        boolean right = isValidBST(root.right);//右
        return left && right;

    }
}