题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
A：在二叉树的后序遍历中，数组最后一个元素为根节点，左子树序列始终小于根节点，右子树序列始终大于根节点
找左子树序列和右子树序列
递归调用查找即可，若不满足条件返回false，若最后left大于right返回true
class Solution {
public:
bool isBST(vector<int> sequence, int left, int right)
{
if(left >= right) //left==right对应的是叶子结点，left>right对应空树
{
return true;
}
int check_right = right;
//找右子树，tmp为右子树最左分界点
while((check_right > left) && (sequence[check_right - 1] > sequence[right]) )
{
--check_right;
}
//找左子树
for(int check_left = check_right - 1; check_left >= left; --check_left)
{
if(sequence[check_left] > sequence[right])
{
return false;
}
}
return (isBST(sequence, left, check_right - 1) && isBST(sequence, check_right, right - 1));
}
bool VerifySquenceOfBST(vector<int> sequence) {
//{5,7,6,9,11,10,8}
if(sequence.empty())
{
return false;
}
return isBST(sequence, 0, sequence.size() - 1);
}
};
相关题目：
计算器：
原文：https://www.cnblogs.com/xiexinbei0318/p/11432867.html