二叉搜索树的后序序列
C++，后序序列的规律。
后序序列的组成一定是[左子树，右子树，根结点]，再根据BST的规律，左 < 根 < 右，
就可以先找出左子树序列，右子树序列，根结点其实就是最后的结点。如果是合法的后序序列的话，必然满足所有左子树序列都小于根结点，所有右子树序列都大于根结点。
根据如上规律，可以递归每棵子树的序列，然后检查子树是否符合后序序列规律。
所以代码如下：
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.empty()) return false;
return dfs(sequence, 0, sequence.size() - 1);
}
bool dfs(vector<int> &v, int left, int right) {
if (left + 1 >= right) return true;
int left_right = right - 1;
for (; left_right >= left; left_right--)
if (v[left_right] < v[right])
break;
for (int i = left_right - 1; i >= left; i--)
if (v[i] > v[right])
return false;
return dfs(v, left, left_right) && dfs(v, left_right + 1, right - 1);
}
};
