[1,3,2]
true
是上图的后序遍历 ，返回true
[3,1,2]
false
不属于上图的后序遍历，从另外的二叉搜索树也不能后序遍历出该序列 ，因为最后的2一定是根节点，前面一定是孩子节点，可能是左孩子，右孩子，根节点，也可能是全左孩子，根节点，也可能是全右孩子，根节点，但是[3,1,2]的组合都不能满足这些情况，故返回false
[5,7,6,9,11,10,8]
true
/* 思路清晰的代码 -- 递归方式 */
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence)
{
if(sequence.empty()) return false;
int root = sequence[sequence.size()-1]; // 找到根节点
// 在二叉搜索树中左子树的结点小于根节点
vector<int> leftSequence;
int i = 0;
for(i = 0;i<sequence.size()-1;i++){
if(sequence[i] < root)
leftSequence.push_back(sequence[i]);
else
break;
}
// 在二叉搜索树中右子树的结点大于根节点
vector<int> rightSequence;
for(int j = i;j<sequence.size()-1;j++){
if(sequence[j] > root)
rightSequence.push_back(sequence[j]);
else
return false;
}
// 如果左子树不为空，则判断左子树是否满足
bool left = true;
if(!leftSequence.empty())
left = VerifySquenceOfBST(leftSequence);
// 如果右子树不为空，则判断右子树是否满足
bool right = true;
if(!rightSequence.empty())
right = VerifySquenceOfBST(rightSequence);
return (left&&right);
}
};
/* 非递归方式 注：该代码抄袭于x楼（作者：SevenYears），感觉无论是代码还是思路都挺好，便引了过来，学习了！
非递归也是一个基于递归的思想：
左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，right部分的
最后一个数字是右子树的根他也比左子树所有值大，因此我们可以每次只看有子树是否符合条件
即可，即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理
对于左子树回到了原问题，对于右子树，左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树只需看看右子树的右子树是否符合要求即可 */ class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence)
{
int size = sequence.size();
if(0 == size) return false;
int i = 0;
while(--size){
while(sequence[i++] < sequence[size]);
while(sequence[i++] > sequence[size]);
if(i < size) return false;
i = 0;
}
return true;
}
};
# -*- coding:utf-8 -*- class Solution: def VerifySquenceOfBST(self, sequence): # write code here if not sequence: return False return self.helper(sequence) # 增加helper函数是因为对于递归来说sequence为空可以作为终止条件，而对于判断BST而言 sequence为空是False def helper(self, sequence): if not sequence: return True root = sequence[-1] for i in range(len(sequence)): if sequence[i] > root: break for right in sequence[i:-1]: if right < root: return False return self.helper(sequence[:i]) and self.helper(sequence[i:-1])
递归遍历
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0){
return false;
}
if(sequence.length == 1){
return true;
}
return search(sequence,0,sequence.length-1);
}
public boolean search(int [] seq , int start, int end ){
//遍历完数组的一部分，没报错，返回true
if(start > end ){
return true;
}
int i = end;
//i从最后往前倒，一直找到第一个比当前根节点小的数，从这个数开始将字符串分为前后两部分
while(i>start && seq[i-1] > seq[end]){
i--;
}
//前办部门如果有比根节点大的数，返回false
for(int j=0;j<i-1;j++){
if(seq[j] > seq[end]){
return false;
}
}
//遍历数组的前半部分和后半部分
return search(seq,start,i-1)&&search(seq,i,end-1);
}
}
/**
* T: 二叉搜索树的后序遍历序列
*
* 题目描述
* 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
* 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
*
* date: 2015.11.28 10:43
* @author SSS
*
*/
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0) {
return false;
}
boolean flag = this.isBST(sequence, 0, sequence.length - 1);
return flag;
}
/**
* 递归实现检测
*
* 对于后序遍历来说，序列数组的最后一个元素一定是根节点,
* 则根据这个元素，将前面的数组分为左、右两个部分，左侧部分都小，右侧部分都大，
* 如果右侧部分有比该根节点小的元素，那么就不是后序遍历,如此递归进行
* @param arr
* @param start
* @param end
* @return
*/
public boolean isBST(int []arr, int start, int end) {
if (start >= end) {
return true;
}
// 当前数组(从start到end部分)的根节点
int curElement = arr[end];
int splitIndex;
// 找到比curElement大和比curElement小的分界点,分成左侧、右侧两组数据
for(splitIndex = start; splitIndex < end && arr[splitIndex] < curElement;splitIndex ++);
// 只需要看右侧即可，因为前面的for循环，已经确保左侧部分全部都小于curElement
for (int i = splitIndex; i < end; i++) {
if (arr[i] < curElement) {
return false;
}
}
return isBST(arr, start, splitIndex - 1) && isBST(arr, splitIndex, end - 1);
}
}
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if len(sequence) == 0:
return False
root = sequence[-1]
# 在二叉搜索中左子树的结点小于跟结点
i = 0
for node in sequence[:-1]:
if node > root:
break
i += 1
# 在二叉搜索中右子树的结点小于跟结点
for node in sequence[i:-1]:
if node < root:
return False
# 判断左子树是不是二叉搜索树
left = True
if i > 1:
left = self.VerifySquenceOfBST(sequence[:i])
right = True
if i < len(sequence) - 2 and left:
right = self.VerifySquenceOfBST(sequence[i+1:-1])
return left and right
import java.util.Arrays;
public class Solution {
public static boolean VerifySquenceOfBST(int[] sequence) {
if(sequence==null||sequence.length==0)
return false;
int root=sequence[sequence.length-1];
int i=0;
for(;i<sequence.length-1;i++){
if(sequence[i]>root){
break;
}
}
int j=i;
for(;j<sequence.length-1;j++){
if(sequence[j]<root)
return false;
}
boolean left=true;
boolean right=true;
if(i>0){
left=VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
}
if(i<sequence.length-1)
right=VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length-1));
return (left&&right);
}
}
class Solution:
def VerifySquenceOfBST(self, sequence):
size = len(sequence)
if size == 0:
return False
size -= 1
index = 0
while size:
while index < size and sequence[index] < sequence[size]:
index += 1
while index < size and sequence[index] > sequence[size]:
index += 1
if index < size:
return False
index = 0
size -= 1
return True
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length == 0) {
return false;
}
return valid(sequence, 0, sequence.length-1, 0x7fffffff);
}
private boolean valid(int[] sequence, int start, int end, int max) {
if (start > end) {
return true;
}
int root = sequence[end];
if (root > max) {
return false;
}
int i = end;
for (; i - 1 >= start && sequence[i - 1] > root; i--);
return valid(sequence, start, i-1, root) && valid(sequence, i, end-1, max);
}
} 
import bisect
class Solution:
def VerifySquenceOfBST(self, sequence):
if not sequence:
return False
def verify(sequence):
if not sequence:
return True
pos = bisect.bisect_right(sequence[:-1], sequence[-1])
left, right = sequence[:pos], sequence[pos:-1]
for i in left:
if i > sequence[-1]:
return False
for i in right:
if i < sequence[-1]:
return False
return verify(left) and verify(right)
return verify(sequence)
递归是个好东西
class Solution {
public:
bool fun(vector<int> s){
if(!s.size()) return true;
int root = s[s.size()-1], i = 0;
while(s[i] < root) i++;
for(int j = i; j < s.size(); j++) if(s[j] < root) return false;
return fun(vector<int> (s.begin(), s.begin()+i))&&
fun(vector<int> (s.begin()+i, s.end()-1));
}
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size() == 0) return false;
return fun(sequence);
}
};
# -*- coding:utf-8 -*- class Solution: def VerifySquenceOfBST(self, sequence): # write code here if not sequence: return False root=sequence[-1] for i in range(len(sequence)): if sequence[i]>root: break for j in range(i,len(sequence)): if sequence[j]<root: return False left=right=True if i>1: left=self.VerifySquenceOfBST(sequence[0:i]) if i<len(sequence)-1: right=self.VerifySquenceOfBST(sequence[i:-1]) return left and right
# -*- coding:utf-8 -*- class Solution: def VerifySquenceOfBST(self, sequence): if sequence == []: return False if len(sequence) == 1 or len(sequence) == 2: return True else: root = sequence.pop(-1) sign = 0 for i in range(len(sequence)): if sequence[i] > root: sign = 1 if (sign == 1) and (sequence[i] < root): return False return self.VerifySquenceOfBST(sequence[:i]) and self.VerifySquenceOfBST(sequence[i:]) # write code here
public static boolean VerifySquenceOfBST(int [] sequence) {
//鲁棒性
if(sequence == null || sequence.length <= 0) return false;
if(sequence.length == 1) return true;
int len = sequence.length;
int i = 0;
while(--len > 0) {//满足每个root 左边的节点 < root,右边的节点>root
while(sequence[i] < sequence[len]) ++i;//i指向右子树的根节点
while(sequence[i] > sequence[len]) ++i;//计算右子树的个数(右子树全部大于root)
if(i < len) return false; //若满足命题2的条件，那么i == len
i = 0;//重置计数器
}
return true;
}
class Solution {
public:
bool isBTree(vector<int> sequence,int l,int r)
{
if(r <= l)
return true;
//左子树都小于根节点
int i=l;
for( ;i<r;i++)
{
if(sequence[i]>sequence[r])
{
break;//不满足左子树条件则跳出
}
}
//右子树都大于根节点
for(int j=i;j<r;j++)
{
if(sequence[j]<sequence[r])
{
return false;//不满足右子树条件返回false
}
}
return isBTree(sequence,l,i-1) && isBTree(sequence,i,r-1);
}
bool VerifySquenceOfBST(vector<int> sequence) {
if(0 >= sequence.size())
return false;
return isBTree(sequence,0,sequence.size()-1);
}
};
/*
//递归
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int size = sequence.size();
if(0==size)
{
return false;
}
return isLastOrder(sequence, 0, size-1);
}
private:
bool isLastOrder(vector<int>& sequece, int b, int e)
{
if(b==e)
{
return true;
}
int mid = b;
while(sequece[mid++]<sequece[e] && mid<e);
int tmp = mid;
while (sequece[tmp++]>sequece[e] && tmp<e);
if(tmp<e)
{
return false;
}
if(mid==b || mid==e)
{
return isLastOrder(sequece, b, e-1);
}
else
{
return (isLastOrder(sequece, b, mid-1) && isLastOrder(sequece, mid, e-1));
}
}
};*/
//非递归
//非递归也是一个基于递归的思想：
//左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，right部分的
//最后一个数字是右子树的根他也比左子树所有值大，因此我们可以每次只看有子树是否符合条件
//即可，即使到达了左子树左子树也可以看出由左右子树组成的树还想右子树那样处理
//对于左子树回到了原问题，对于右子树，左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树
//只需看看右子树的右子树是否符合要求即可
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int size = sequence.size();
if(0==size)return false;
int i = 0;
while(--size)
{
while(sequence[i++]<sequence[size]);
while(sequence[i++]>sequence[size]);
if(i<size)return false;
i=0;
}
return true;
}
};
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);
}
} 序列最后一位为根节点
递归判断左右子树的合法性
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence:
return False
root = sequence[-1]
valid = False # 到达右子树的标志
tar = -1 # 左子树的范围
for i,_ in enumerate(sequence[:-1]):
if _ > root: # 右子树部分
valid = True
elif valid: # 在右子树出现比root小的树
return False
else: # 左子树部分
tar = i
left = True if tar == -1 else self.VerifySquenceOfBST(sequence[:tar+1])
right = True if not valid else self.VerifySquenceOfBST(sequence[tar+1:-1])
return left and right
//import java.util.ArrayList;
public class Solution {
//public boolean res = true;
public boolean VerifySquenceOfBST(int [] sequence) {
//ArrayList<Integer> arr = new ArrayList<Integer>();
if (sequence.length == 0) {
return false;
}
if (sequence.length == 1) {
return true;
}
return bs(sequence, 0, sequence.length - 1);
}
public boolean bs(int [] arr, int start, int end) {
if (start >= end) {
return true;
}
int j = end - 1;
while (j >= start) {
if (arr[j] < arr[end]) {
break;
}
j--;
}
if (j < 0) {
return true;
}
for (int i = j; i >= start; i--) {
if (arr[i] > arr[end]) {
return false;
}
}
return bs(arr, 0, j) && bs(arr, j + 1, end - 1);
}
}
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.empty()) return false;
int last = sequence.back();
auto it = find_if(sequence.begin(), sequence.end(), [last](int c) {return c >= last;});
vector<int> left(sequence.begin(), it);
vector<int> right(it, sequence.end() - 1);
if (!right.empty() && any_of(right.begin(), right.end(), [last](int c) {return c < last;})) return false;
return (left.empty() || VerifySquenceOfBST(left)) && (right.empty() || VerifySquenceOfBST(right));
}
};
扫描二维码，关注牛客网
下载牛客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); } };