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

方法一：递归

• 较自然的思路，遵循后序遍历的规则:左子树->右子树->根节点。因此当前序列的最后一个值即为根节点，且左子树<根节点<右子树。每次遍历当前序列，根据大小顺序判断是否符合条件，同时得到左右子树序列，并递归调用函数判断子树序列是否符合条件。

  class Solution {
  public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0) 
            return false;
        return helper(sequence,0,sequence.size()-1);
    }
    //辅助递归函数，判断当前树是否为二叉树的后序遍历序列。
    bool helper(vector<int> sequence,int start,int end){
        if(start>=end) 
            return true;
        int lStart=start,i=start;
        while(sequence[i]<sequence[end])
            i++;
        int lEnd=i-1,rStart=i;
        while(sequence[i]>sequence[end])
            i++;
        //序列不符合前半部分小于sequence[end],后半部分大于sequence[end]的条件
        //--->说明当前序列不是二叉搜索树的后序遍历。
        if(i!=end)
            return false;
        int rEnd=end-1;
        return helper(sequence,lStart,lEnd)&&helper(sequence,rStart,rEnd);
    }
  };

  复杂度分析：

  时间复杂度：O(n^2),时间复杂度来源于调用helper函数的次数，以及每次调用时的时间开销，前者是固定的，即O(n),后者取决于二叉搜索树的形状，当二叉搜索树每层只有一个节点时，即变成了一个链表，为O(n)，总O(n^2)。
  空间复杂度：O(n),取决于递归的深度，同上，深度最大，即变成链表时，O(n)。

方法二：

• 题目中的要点在于两个：后序遍历，二叉搜索树。我们模拟后序遍历的过程，来判断每时每刻的状态是否满足二叉搜索树。
  从后往前遍历，即顺序变成了根->右子树->左子树。由于右子树>根>左子树，所以当该序列有下降时，说明当前已经来到了左子树，找到大于当前值的最小值，该值即为局部树中的根节点。初始时，令根节点root无穷大，则当前树为该根节点的左子树。遍历过程中，逐步缩小root的值，因为所有的操作都是在当前根节点root的左子树中进行的，所以保证遍历的值小于root即可满足判断条件，否则为false；

  代码如下：

  class Solution {
  public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0)
            return false;
        stack<int> s;
        int root=1000000;
        //序列从后往前遍历，即根->右子树->左子树的顺序。
        for(int i=sequence.size()-1;i>=0;i--){
            //不满足二叉搜索树所表现出来的特征，即存在左子树中节点值大于根节点。
            if(sequence[i]>root)
                return false;
            //找到栈中大于当前值sequence[i]的最小值 即为root
            while(!s.empty()&&sequence[i]<s.top()){
                root=s.top();
                s.pop();
            }
            s.push(sequence[i]);
        }
        return true;
    }   
  };

图解如下：

复杂度分析：

时间复杂度：O(n),遍历数组序列。
空间复杂度：O(n),入栈最大数目n。