文章目录
- 题目
- 方法一：BFS 层序遍历
- 方法二： 递归
- 方法三： 中序遍历（栈）
- 方法四： 中序遍历（递归）
题目
思路就是首先得知道什么是二叉搜索树
左孩子在（父节点的最小值，父节点）区间内
右孩子在（父节点，父节点的最大值）区间内
只要满足这两点就行
方法一：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);
//判断左子树 和右子树是否是搜索二叉树
// ==左孩子在（父节点的最小值，父节点）区间内==
// ==右孩子在（父节点，父节点的最大值）区间内==
}
方法三： 中序遍历（栈）
- 核心先遍历左子树，直到左子树为null 再去遍历右子树，直到右子树为null
- 每弹出一个节点的值小于等于前一个 inorder，说明不是二叉搜索树
- 在遍历右子树的同时 更新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;
}
