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

#include <vector>
class Solution {
  public:
    //思路：虽然我们无法只靠后序遍历的结果就完整地构建出一棵树，但是既然有了二叉搜索树的这一限定条件（题目只说只要这个后序遍历的结果能满足是某一个二叉搜索树的遍历结果就行，也就是说，重点是放在符合二叉搜索树的定义，而不是构建出原本的树上），我们就只用专心于判断是否满足二叉搜索树的定义即可。
    //递归地判断每一棵子树是否满足定义。
    bool solve(int begin, int end, vector<int>& seq) {
        if (begin == end)
            return true;
        int root = seq[end]; //后序遍历的结果中，最后一个被访问到的是根节点。
        int LesserThanRootCount = 0;
        int GreaterThanRootCount = 0;
        int i = 0;
        for (i = end - 1; i >= begin; i--) {
            if (seq[i] > root) {
                GreaterThanRootCount++;
            } else {
                LesserThanRootCount++;
            }
        }
        if (GreaterThanRootCount == 0 || LesserThanRootCount==0) {
            //左右子树一边为全空的情况。在我们上面的判断中，只有全大于root或全小于Root才会出现这种情况，因此这时root树本身肯定算是满足二叉搜索树的定义了，只要去看它的子树是否满足即可。
            return solve(begin, end-1, seq);
        }

        int leftRoot = begin;
        int rightRoot = end - 1; //后序遍历中，根节点分出的左右两棵子树，其中右子树就是紧挨在根节点左边，因此rightRoot就是end-1，而左子树在的位置还得找找。
        //寻找左子树根的位置。找到后我们才能明确出begin~leftRoot是左子树的范围，rightRoot~end-1是右子树的范围。
        i = 0;
        for (i = end - 1; i >= begin; i--) {
            if (seq[i] < root) {
                leftRoot = i;
                break;
            }
        }
        //判断右子树是否满足全部大于root的条件。
        for (i = end - 1; i > leftRoot; i--) {
            if (seq[i] <= root) {
                return false;
            }
        }
        for (i = leftRoot;i>=begin;i--)
        {
            if(seq[i]>=root)
                return false;
        }
        //熬过了重重考验，现在可以认定这棵root树大体上是满足二叉搜索树的定义，但还要检查它的子树是否满足。
        return solve(begin,leftRoot,seq) && solve(leftRoot+1,end-1,seq);
    }

    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())
            return false;
        return solve(0,sequence.size()-1,sequence);
    }
};