题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
python实现：
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST1(self, sequence):
# write code here
#二叉搜索树的特性
n = len(sequence)
if n==0:
return False
if n==1:
return True
if sequence[0]>sequence[-1]:#没有左子树
for i in range(1, n-1):
if sequence[i]<sequence[-1]:
return False
return self.VerifySquenceOfBST(sequence[:-1])
rightStart = n-1
for i in range(1, n-1):
if sequence[i]>sequence[-1]:
rightStart = i
else:
if rightStart<n-1:
return False
if rightStart==n-1:#没有右子树
return self.VerifySquenceOfBST(sequence[:-1])
else:
return self.VerifySquenceOfBST(sequence[:rightStart]) and self.VerifySquenceOfBST(sequence[rightStart:-1])
#写法2：
def VerifySquenceOfBST(self, sequence):
n = len(sequence)
if n==0:
return False
if n==1:
return True
root = sequence[-1]
leftEnd = -2
rightStart = n-1
for i in range(n-1):
if sequence[i]>root:
if rightStart==n-1:
rightStart = i
leftEnd = i-1
else:
if leftEnd!=-2:
return False
left = True
if leftEnd>=0:#有左子树
left = self.VerifySquenceOfBST(sequence[:leftEnd+1])
right = True
if rightStart<n-1:#有右子树
right = self.VerifySquenceOfBST(sequence[rightStart:-1])
return left and right
c++实现：
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
return verify(sequence, 0, sequence.size()-1);
}
bool verify(vector<int> &sequence, int start, int end){
if((end-start+1)==0)
return false;
int root=sequence[end];
int leftEnd=start-2, rightStart=end;
for(int i=start;i<end;i++){
if(sequence[i]<root){
if(leftEnd!=start-2)//已经找到左子树终点，现在又遇到比跟小的数
return false;
}else{
if(rightStart==end){//还没找到右子树
rightStart = i;
leftEnd=i-1;//rightStart=0时leftEnd=-1,这也是为什么leftEnd初始化为2的原因
}
}
}
bool left=true;
if(leftEnd>=start)//有左子树
left = verify(sequence, start, leftEnd);
bool right=true;
if(rightStart<end)//有右子树
right = verify(sequence, rightStart, end-1);
return (left && right);
}
};
转载请注明原文地址: https://ju.6miu.com/read-1200205.html
