力扣【98. 验证二叉搜索树】Java题解（容易写错的题）

二叉搜索树的中序遍历是有序数组（因为对于数组某个元素，左边是它的左子树而右边是它的右子树，显然二叉树搜索树左子树小于它，右子树大于它），所以可以直接中序遍历然后判断是否有序来判断是否是二叉搜索树。

但是在实际代码中，我们可以不用把元素保存在数组中，只需在每个节点遍历的时候和上一个节点的值比较即可。而这个过程需要设置一个全局变量，表示上一个节点的值，然后每次进行比较然后设置即可，而初始化则为Long.MIN_VALUE（因为测试用例中有int的最小值）

class Solution {
    long num = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(find(root) == false) return false;
        return true;
    }
    public boolean find(TreeNode node){
        if(node == null) return true;
        if(find(node.left) == false) return false;
        if(num >= node.val) return false;
        num = node.val;
        return find(node.right);
    }
}

其实我们也可以直接保存上一个节点作为全局变量和当前节点进行比较，这样就不用担心类型数据范围的问题。变量初始化为null。

class Solution {
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        return find(root);
    }
    public boolean find(TreeNode node){
        if(node == null) return true;
        if(find(node.left) == false) return false;
        if(pre != null && pre.val >= node.val) return false;
        pre = node;
        return find(node.right);
    }
}