题目是关于二叉搜索树的后序遍历,我们需要了解二叉搜索树的左子树所有的值小于根节点,右子树的值大于根节点,而后序遍历数组的最后一个值为根节点,判定数组中小于根节点的为其左子树,大于根节点的为其右子树,然后就是其递归判定左子树和右子树;
牛客网剑指offer在线编程通过代码:
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { int length=sequence.size(); vector<int>s_left,s_right; if(length==0) return false; int root=sequence[length-1]; int i=0; for(i=0;i<length-1;i++) { if(sequence[i]>root) break; s_left.push_back(sequence[i]); } int j=i; for(;j<length-1;j++) { if(sequence[j]<root) return false; s_right.push_back(sequence[j]); } bool left=true; if(s_left.size()>0) left=VerifySquenceOfBST(s_left); bool right=true; if(s_right.size()>0) right=VerifySquenceOfBST(s_right); return (left&&right); } };