- 题目:输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
- 思路:使用递归,去判断左右子树对应的序列是否满足二叉搜索树的定义。右子树的数都比左子树的大且比当前节点大,因此如果找到第一个值大于value的下标index(左右子树的分界线)以后,后边的数应该都比value大(因为右子树都大于value)。如果找到index后还有数小于value,则不是一个后续遍历序列。因为是后序序列,因此中间节点在最后边。
- 注意:因为假如有右子树时,index初始值会被重新赋值,怎么初始化index都没有影响。假如只有左子树时所有数字都比value小,那么index应该为high。综上,index初始化为high。
- code
class Solution {
public:
bool isPost(vector<int> seq, int low, int high){
if (high<=low) return true;
int value = seq[high];
int index = high;
for (int i = low; i < high; i++){
if (seq[i]>value){
index = i;
break;
}
}
if (index<high){
for (int i = index+1; i < high; i++){
if (seq[i]<value) return false;
}
return isPost(seq, low, index-1) && isPost(seq, index, high-1);
}
return true;
}
bool VerifySquenceOfBST(vector<int> seq) {
int len = seq.size();
if (!len) return false;
return isPost(seq, 0, len-1);
}
};