方法一:递归

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