[1,3,2]
true
是上图的后序遍历 ，返回true
[3,1,2]
false
不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false
[5,7,6,9,11,10,8]
true
import java.util.*;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0) return false;
return isValid(sequence);
}
private boolean isValid(int[] seq) {
if (seq.length <= 1) {
return true;
}
int rootVal = seq[seq.length - 1];
int idx = 0; // 左右子树分割点
while (seq[idx] < rootVal && idx < seq.length) {
idx++;
}
for (int i = idx; i < seq.length - 1; i++) {
if (seq[i] < rootVal) {
return false;
}
}
int[] leftSeq = Arrays.copyOfRange(seq, 0, idx);
int[] rightSeq = Arrays.copyOfRange(seq, idx, seq.length - 1);
return isValid(leftSeq) && isValid(rightSeq);
}
} 
import java.util.*;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if (!(sequence.length > 0)) {
return false;
}
// Storage all child tree
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(sequence);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] nodes = queue.poll();
// System.out.println(Arrays.toString(nodes));
if (nodes.length <= 1) {
break;
}
int root = nodes[nodes.length - 1];
// System.out.println("root = " + root);
// Finding right bound of left tree
int leftIndex = -1;
for (int j = 0; j < nodes.length; j++) {
int node = nodes[j];
if (node < root && j > leftIndex) {
leftIndex = j;
}
}
// Left tree found
if (leftIndex >= 0) {
int[] leftNodes = Arrays.copyOfRange(nodes, 0, leftIndex + 1);
// System.out.println("leftNodes = " + Arrays.toString(leftNodes));
int[] sortedLeftNodes = Arrays.copyOf(leftNodes, leftNodes.length);
Arrays.sort(sortedLeftNodes);
int maxOnLeft = sortedLeftNodes[sortedLeftNodes.length - 1];
// All child nodes should less than root
if (maxOnLeft > root) {
return false;
}
queue.offer(leftNodes);
int rightIndex = nodes.length - 1 - 1;
int[] rightNodes = rightIndex > leftIndex
? Arrays.copyOfRange(nodes, leftIndex + 1, rightIndex + 1)
: null;
// Right bound of left tree < Left bound of right tree, right tree exist
if (rightNodes != null) {
// System.out.println("rightNodes = " + Arrays.toString(rightNodes));
int[] sortedRightNodes = Arrays.copyOf(rightNodes, rightNodes.length);
Arrays.sort(sortedRightNodes);
int minOnRight = sortedRightNodes[0];
// All child nodes should > root
if (minOnRight < root) {
return false;
}
queue.offer(rightNodes);
}
} else {
// Might be left tree&nbs***bsp;right tree
int[] childNodes = Arrays.copyOfRange(nodes, 0, nodes.length - 1);
// System.out.println("childNodes = " + Arrays.toString(childNodes));
queue.offer(childNodes);
}
}
}
return true;
}
}
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0){
return false;
}
return order(sequence,0,sequence.length-1);
}
public boolean order(int[] sequence,int left, int right){
if(left >= right) return true;
int root = sequence[right]; //根节点为最后一个元素
// 找到左右子树的分界点，第一个大于根节点的元素位置
int mid = 0;
for(int i=left;i<right;i++){
if(sequence[i]>root){
mid = i;
break;
}
}
// 判断右子树合不合法
for(int i=mid;i<right;i++){
if(sequence[i]<root){ //右子树存在小于root的元素则为false
return false;
}
}
return order(sequence,left,mid-1) && order(sequence,mid,right-1);
}
} 
public class Solution {
public boolean VerifySquenceOf(int [] sequence,int start,int end)
{
if(start>=end)
return true;
int root=sequence[end];
int i=start;
while(i<=end&&sequence[i]<root)
{
i++;
}
for(int j=i;j<end;j++)
{
if(sequence[j]<root)
return false;
}
return VerifySquenceOf(sequence,start,i-1) && VerifySquenceOf(sequence,i,end-1);
}
public boolean VerifySquenceOfBST(int [] sequence)
{
if(sequence==null || sequence.length==0)
return false;
return VerifySquenceOf(sequence,0,sequence.length-1);
}
} 
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence.length == 0) {
return false;
}
return VerifySquenceOfBSTCore(sequence, 0, sequence.length - 1);
}
private boolean VerifySquenceOfBSTCore(int[] sequence, int start, int end) {
//在不断查找过程中，区域不断缩小，为空时，证明之前的所有范围都满足检测条件
// 也就是是一个BST
if (start >= end) {
return true;
}
//拿到root节点的值
int root = sequence[end];
//先遍历左半部分，也就是整体都要比root小，拿到左子树序列
int i = start;
while (i < end && sequence[i] < root) {
i++;
}
//在检测右子树是否符合大于root的条件,要从i开始，也就是右半部分的开始
for (int j = i; j < end; j++) {
if (sequence[j] < root){
return false;
}
}
//走到这里，就说明，当前序列满足需求。但并不代表题目被解决了，还要在检测left和right各自是否也满 足
return VerifySquenceOfBSTCore(sequence,start,i-1) && VerifySquenceOfBSTCore(sequence,i,end-1);
}
} 
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
//递归方式
if(sequence == null || sequence.length == 0) return false ;
if(sequence.length == 1) return true;
//后序遍历 数组最后一个元素是头节点 然后因为这是二叉搜索树 所以左子树小于根 右子树大于根
//根据这个原理进行递归判断
return recursion(sequence,0,sequence.length - 1);
}
private boolean recursion(int[] arr,int start , int end){
if(start > end) return true ; //说明遍历完了 都没有是false的 返回true
int i = start ;
//拿到左子树的元素位置
while(arr[i] < arr[end]){
++i;
}
//如果右子树的部分遍历过程中有小于根节点的 直接返回false
for(int j = i ; j < end ; j++){
if(arr[j] < arr[end]) {
return false ;
}
}
return recursion(arr,start,i-1) && recursion(arr,i,end - 1);
}
} 
import java.util.*;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0) return false;
return jiaoyan(sequence);
}
public boolean jiaoyan(int[] sequence){
// 递归终止条件:数组为空停止。
if(sequence.length<1) return true;
int index=0;
// 获取根节点
int root = sequence[sequence.length-1];
// 先找一个左右子树的分界值
while(index<sequence.length-1){
if(sequence[index]>root){
break;
}
index++;
}
// 程序能执行到此处，说明index 左边的元素全是左子树， index 右边的元素全是右子树
// 先校验右子树中是否全部元素大于根。
int temp = index;
while(temp<sequence.length-1){
if(sequence[temp]<root){
return false;
}
temp++;
}
// 递归校验左子树
boolean left = jiaoyan(Arrays.copyOfRange(sequence,0,index));
// 递归校验右子树
boolean right = jiaoyan(Arrays.copyOfRange(sequence,index,sequence.length-1));
return left && right;
}
} 
private boolean verify(int[] sequence, int first, int last) {
// 递归终止条件
if (last - first <= 1) {
return true;
}
// 后序遍历:“左子树-右子树-根节点”，所以rootVal是根值
int rootVal = sequence[last], cutIndex = first;
// 左子树均小于根值
while (cutIndex < last && sequence[cutIndex] < rootVal) {
//(由于你不清楚数组哪一部分是左子树，就先把小于根值的都划归左子树，这样剩下的都成了右子树，咱们就判断右子树是否合规)
cutIndex++;
}
// 右子树均大于根值
for (int i =cutIndex; i < last; i++) {
if (sequence[i] < rootVal) {
return false;
}
}
// 递归
return verify(sequence, first, cutIndex - 1) && verify(sequence, cutIndex, last - 1);
}
public boolean verifySequenceOfBST(int[] sequence) {
// 判空
if (sequence == null || sequence.length == 0) {
return false;
}
// 二叉排序树BST：左 < 中 < 右
return verify(sequence, 0, sequence.length - 1);
}
题目不满足小驼峰命名法，行，我忍了 
public static boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0 ) {
return false;
}
return VerifySquenceOfBST(sequence, 0, sequence.length -1 );
}
private static boolean VerifySquenceOfBST(int[] sequence, int start, int end) {
if (start > end) {
return true;
}
//最后一个是root节点
int root = sequence[end];
//从左向右，找到小于root节点的，认为是左子树，其他的认为是右子树，都要>root 节点
int left = start;
while (left < end && sequence[left] < root) {
left++;
}
//右子树都要> root,否则返回false
int right = left +1;
while (right < end) {
if (sequence[right++] < root) {
return false;
}
}
return VerifySquenceOfBST(sequence, start, left -1) && VerifySquenceOfBST(sequence,left, end -1);
} 
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0) return false;
return dfs(sequence,0,sequence.length-1);
}
public boolean dfs(int [] sequence,int start,int end){
if(start>=end) return true;//表示为1个数字
int midval=sequence[end];
int i=start;
while(i<end&&sequence[i]<midval){
i++;
}
boolean leftrst=true;
if(i!=start){//左子树不为空
leftrst=dfs(sequence,start,i-1);
}
for(int p=i;p<end;p++){//右子树存在大于mid的值,不为后续遍历 返回false
if(sequence[p]<midval){
//rightrst=false;
return false;
}
}
boolean rightrst=dfs(sequence,i,end-1);
return leftrst&&rightrst;
}
} 
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length == 0)
return false;
return verify(sequence, 0, sequence.length-1);
}
//利用递归循环看左子树和右子树是否所有的值都符合要求
public boolean verify(int[] seq, int l, int r) {
//如果左右重合，说明只剩一个数了，说明之前的数都符合BST规则
if (l >= r)
return true;
//找根
int root = seq[r];
//找出左右子树分界点
int i = r-1;
while (i >= l) {
if(seq[i] < root)
break;
i--;
}
int j = i+1;
int index = i;
//循环看左右子树是否符合规则
while(i >= l) {
if (seq[i--] > root)
return false;
}
while(j < r) {
if (seq[j++] < root)
return false;
}
//递归检查其余的数是否符合规则
return verify(seq, l, index) && verify(seq, index+1, r-1);
}
} 
public class Solution {
//左子树都应该小于根节点的值，按照此规律先找到左子树的最后一个节点
//后面是右子树的值，应该都大于根节点的值
//递归
public boolean VerifySquenceOfBST(int [] sequence) {
int len = sequence.length;
if(len == 0) return false; //该题约定空树不是BST
return help(sequence, 0, len - 1);
}
public boolean help(int [] sequence, int start, int end) {
if(start >= end) return true;
int root = sequence[end];
int index = -1;
//退出循环时，index指向左子树的最后一个节点
for(int i = 0; i < end; i++) {
if(sequence[i] < root) { //无重复的元素
index++;
}
}
//if(index == -1) 也可能没有左子树，不过到下一次递归函数中会处理
for(int i = index + 1; i < end; i++) {
if(sequence[i] < root) {
return false;
}
}
return help(sequence, start, index) &&
help(sequence, index + 1, end - 1);
}
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
class Solution { bool judge(vector<int>& a, int l, int r){ if(l >= r) return true; int i = r; while(i > l && a[i - 1] > a[r]) --i; for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false; return judge(a, l, i - 1) && (judge(a, i, r - 1)); } public: bool VerifySquenceOfBST(vector<int> a) { if(!a.size()) return false; return judge(a, 0, a.size() - 1); } };