题解 | #二叉搜索树的后序遍历序列#

1. BST的特点是对任意结点，左子树小于该结点，右子树大于该结点。

2. 后序遍历产生的序列为左子树-右子树-结点。

3. 所以可知后序遍历序列的最后一个元素即为BST的根，再根据大小规律，可以找到左右子树对应的序列。递归处理这两个序列即可。

4. 找左右子树序列时可采用二分查找法，虽然左右子树序列不是完全有序。

class Solution {
	
public:
	int bSearch(const vector<int> &vec, int beg, int end, int k)
	{
		while (beg <= end)
		{
			int mid = (beg + end) / 2;
			if (k == vec[mid])
			{
				return mid;
			}
			
			if (k < vec[mid])
			{
				end = mid - 1;
			}
			else
			{
				beg = mid + 1;
			}
		}
		
		return beg;
	}
    
	bool search(const vector<int> &vec, int beg, int end)
	{
		if (beg >= end)
		{
			return true;
		}

        cout << beg << "," << end << endl;

        int root = vec[end];
        int loc = bSearch(vec, beg, end - 1, root);
        if (find_if(vec.begin() + beg, vec.begin() + loc, [root](int a){return a >= root;}) != (vec.begin() + loc) 
            || find_if(vec.begin() + loc, vec.begin() + end, [root](int a){return a <= root;}) != (vec.begin() + end))
        {
            cout << "error : " << beg << "," << end << "," << loc << endl;
            return false;
        }
        
		return search(vec, beg, loc - 1) && search(vec, loc, end - 1);
	}
	
    bool VerifySquenceOfBST(vector<int> sequence) {
		if (sequence.empty())
		{
			return false;
		}
        
		return search(sequence, 0, sequence.size() - 1);
    }
};