剑指offer 二叉搜索树的后序遍历序列
- 题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
- 题目解析
首先取出vector中最后一个元素，即为根节点，判断是否前面的一部分元素比她小，后面的一部分元素比她大。然后递归地去判断左边的一部分元素和右边的一部分元素是否满足这个规律。
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int size = sequence.size();
if (size == 0)
return false;
else if (size == 1)
return true;
else{
vector<int> left;
vector<int> right;
int root = sequence[size - 1];
int i = 0;
for (; i < size; ++i){
if (sequence[i]>root)
break;
if (sequence[i] != root)
left.push_back(sequence[i]);
}
for (; i < size; ++i){
if (sequence[i] < root)
return false;
if (sequence[i] != root)
right.push_back(sequence[i]);
}
bool l = true, r = true;
if (left.size()>0)
l = VerifySquenceOfBST(left);
if (right.size()>0)
r = VerifySquenceOfBST(right);
return l&&r;
}
}
};