题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
举例二叉搜索树
难点坑点
- 这道题主要的难点是二叉树的后续遍历的关系，我们可以看到二叉树的根节点一定是序列的最后一个数据；所以此序列满足条件，
- 注意二叉树为空时要返回false
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int max=sequence.size();
int i=0;
if(sequence.empty())
return false;
for(;max>0;max--,i=0){
while(sequence[max]>sequence[i++]);
while(sequence[max]<sequence[i++]);
if(i<max)
return false;
}
return true;
}
};
网友评论