java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

1. 法一：利用BST性质进行递归

解题思路：时间复杂度O(n),空间复杂度O(n)

1. 二叉搜索树必须满足，并且左子树的值都小于当前结点，右子树的值都大于当前结点。
2. 所以我们依次遍历每个结点，并且传入这个结点的合理取值范围。如果它是上一个结点的左孩子，就不能大于父亲。如果它是上一个结点的右孩子，就不能小于父亲

代码

class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}public boolean isValidBST(TreeNode node, long lower, long upper) {if (node == null) return true;//如果node为null，返回trueif (node.val <= lower || node.val >= upper) return false;//如果当前值，小于最小值，或者大于最大值，都不符合二叉搜索树//当前结点的左子树的合理取值范围是，不大于当前结点值，且不小于lower//当前结点右子树的合理取值范围，不小于当前结点，且不大于upper。return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);}
}

2. 法二：利用中序遍历

解题思路：时间复杂度O(n),空间复杂度O(n)

二叉搜索树BST的中序遍历顺序，一定是一个递增的序列，所以中序遍历过程中，判断是否后一个值>前一个值，如果是的话，那么这就不是一课BST

代码

1. 使用一个全局变量，从而使用递归
   

class Solution {private long pre = Long.MIN_VALUE;//保存中序遍历前一个值public boolean isValidBST(TreeNode root) {if (root == null) return true;//如果左子树不符合BST树，或者前一个值>=当前值，则不是BSTif (!isValidBST(root.left) || root.val <= pre)return false;pre = root.val;//当前值变成下一次的prereturn isValidBST(root.right);//然后看右子树}}

2. 不能使用全局变量的情况下，只能用迭代法
   

class Solution {public boolean isValidBST(TreeNode root) {Deque<TreeNode> stack = new LinkedList<TreeNode>();//模拟栈double inorder = -Double.MAX_VALUE;//中序遍历的前一个值while (!stack.isEmpty() || root != null) {//先左while (root != null) {stack.push(root);root = root.left;}//然后中root = stack.pop();// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树if (root.val <= inorder) {return false;}inorder = root.val;//更新inorder//然后右root = root.right;}return true;}
}