思路:
时间复杂度:O(nlogn)
后序遍历序列的最后一个值是根节点,又由于是二叉搜索树,则比根节点值小的在左子树,其余的在右子树。
bool VerifySquenceOfBST(vector<int> sequence) {if(sequence.empty())return false;return isSequenceOfBST(sequence, 0, sequence.size() - 1);}bool isSequenceOfBST(vector<int> sequence, int start, int end){if(start >= end - 1)return true;int mid = 0, i = start;for(;i < end;i++){if(sequence[i] > sequence[end]){mid = i;break;}}for(;i < end;i++){if(sequence[i] < sequence[end])break;}if(i != end)return false;else return isSequenceOfBST(sequence, start, mid - 1) && isSequenceOfBST(sequence, mid, end - 1);}
二叉搜索树可以为空阿!
但是题目中序列为空时输出的是false
