青岛网站制作企业,网站的服务内容,做自己的网站多少钱,猎头公司主要做什么文章目录 题目方法一#xff1a;BFS 层序遍历方法二#xff1a; 递归方法三#xff1a; 中序遍历#xff08;栈#xff09;方法四#xff1a; 中序遍历#xff08;递归#xff09; 题目 思路就是首先得知道什么是二叉搜索树 左孩子在#xff08;父节点的最小值#x… 文章目录 题目方法一BFS 层序遍历方法二 递归方法三 中序遍历栈方法四 中序遍历递归 题目 思路就是首先得知道什么是二叉搜索树 左孩子在父节点的最小值父节点区间内 右孩子在父节点父节点的最大值区间内 只要满足这两点就行
方法一BFS 层序遍历
利用层序遍历 拿到每一个节点 并且给每一个结点配备一个最大值和最小值的队列 只要节点在最大值和最小值之间就满足二叉搜索树的条件 public boolean isValidBST(TreeNode root) {if(root null) return true;QueueTreeNode queue new LinkedList();QueueLong minValues new LinkedList();//定义两个队列来记录每一个节点的最大值和最小值情况 QueueLong 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) {DequeTreeNode stack new LinkedListTreeNode();//栈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;}
