【LeetCode-中等题】98. 验证二叉搜索树

题目

思路就是首先得知道什么是二叉搜索树
左孩子在（父节点的最小值，父节点）区间内
右孩子在（父节点，父节点的最大值）区间内
只要满足这两点就行

方法一：BFS 层序遍历

利用层序遍历 拿到每一个节点 并且给每一个结点配备一个最大值和最小值的队列
只要节点在最大值和最小值之间就满足二叉搜索树的条件

public boolean isValidBST(TreeNode root) {if(root == null) return true;Queue<TreeNode> queue = new LinkedList<>();Queue<Long> minValues = new LinkedList<>();//定义两个队列来记录每一个节点的最大值和最小值情况  Queue<Long> maxValues = new LinkedList<>();queue.offer(root);minValues.offer(Long.MIN_VALUE); // 初始最小值为maxValues.offer(Long.MAX_VALUE); // 初始最大值为while(!queue.isEmpty()){int count = queue.size();for(int i = 0 ; i < count ; i++){TreeNode node =  queue.poll();Long minValue = minValues.poll();//弹出该对比节点的最大值和最小值情况   节点值必须在这个区间内才满足条件Long maxValue = maxValues.poll();if (  node.val <= minValue ||  node.val >= maxValue) {return false;}if(node.left != null){queue.offer(node.left);minValues.offer(minValue);//  左子树的最小值沿用上一次的最小值maxValues.offer((long)node.val); // 左子树的最大值为当前节点值}if(node.right != null){queue.offer(node.right);minValues.offer((long)node.val); // 右子树的最小值为当前节点值maxValues.offer(maxValue); // 右子树的最大值沿用上一次的最大值}}}return true;}

方法二： 递归

	   // root.val要在  （min,max） 区间才是二叉搜索数//  判断左子树 和右子树是否是搜索二叉树   //   ==左孩子在（父节点的最小值，父节点）区间内==// 	  ==右孩子在（父节点，父节点的最大值）区间内==

    public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);   // 不能用Integer.MAX  2147483647  案例有root就等于2147483647  明显不满足搜索树}public boolean isValidBST(TreeNode root,long  min,long  max) {if(root == null ){return true;}if(root.val <= min || root.val >= max) return false;//root.val要在  （min,max） 区间才是二叉搜索数return isValidBST(root.left,min,root.val)&&isValidBST(root.right,root.val,max);//判断左子树 和右子树是否是搜索二叉树   //   ==左孩子在（父节点的最小值，父节点）区间内==// 	  ==右孩子在（父节点，父节点的最大值）区间内==}

方法三： 中序遍历（栈）

1. 核心先遍历左子树，直到左子树为null 再去遍历右子树，直到右子树为null
2. 每弹出一个节点的值小于等于前一个 inorder，说明不是二叉搜索树
3. 在遍历右子树的同时 更新inorder值为当前节点

  public boolean isValidBST(TreeNode root) {Deque<TreeNode> stack = new LinkedList<TreeNode>();//栈Long inorder = Long.MIN_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 = (long)root.val;root = root.right;//遍历右子树}return true;}

方法四： 中序遍历（递归）

中序遍历时，判断当前节点是否大于中序遍历的前一个节点，如果大于，说明满足 BST，继续遍历；否则直接返回 false。

 long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;//判断左子树是不是 二叉搜索时if(!isValidBST(root.left)) return false;if(root.val <= pre) return false ;else pre = root.val;//判断右子树是不是 二叉搜索时if(!isValidBST(root.right)) return false;return true;}