输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。
假设输入的数组的任意两个数字都互不相同。
样例
输入：[4, 8, 6, 12, 16, 14, 10]
输出：true

解法：建树

二叉搜索树，只要知道了前序或者是后序遍历序列，也就知道了中序
有了两个之后，就可以建立一棵树了
所以判断该数组是不是某二叉搜索树的后序遍历的结果，也就是看能否成功建成这棵树
时间复杂度O(nlogn)，空间复杂度O(n)

class Solution {
public:
    unordered_map<int, int> h;
    bool verifySequenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return true;
        vector<int> post = sequence;
        vector<int> in = post;
        sort(in.begin(), in.end());
        for (int i = 0; i < in.size(); i++) {
            h[in[i]] = i;
        }
        return build(in, post, 0, in.size() - 1, 0, post.size() - 1);
    }
    bool build(const vector<int> &in, const vector<int> &post, int il, int ir, int pl, int pr) {
        int root = post[pr];
        int k = h[root];
        if (k > ir || k < il) return false;
        bool flag = true;
        if (il < k) flag &= build(in, post, il, k - 1, pl, pl + k - 1 - il);
        if (k < ir) flag &= build(in, post, k + 1, ir, pl + k - il, pr - 1);
        return flag;
    }
};