剑指offer面试题[24]-二插搜索树的后序遍历序列

亦凉 2022-06-11 01:20 137阅读 0赞

## 题目描述 ##

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

class Solution {
    public:
        bool VerifySquenceOfBST(vector<int> sequence) {
             int len=sequence.size();
             if(sequence.empty()||len<=0)
                 return false;
             int root=sequence[len-1];
             vector<int> LeftSubSeq;
             vector<int> RightSubSeq;
                      
             //在二插搜索树中左子树的结点小于根节点
             int i;
             for(i=0;i<len-1;i++)
               {
                  if(root<sequence[i])
                      break;
                  LeftSubSeq.push_back(sequence[i]);
               }
              
             //在二插搜索树中右子树的结点大于根节点
             int j;         
             for(j=i;j<len-1;j++)
               {
                  if(root>sequence[j])
                      return false;
                  RightSubSeq.push_back(sequence[j]);
               }
             
             //判断左子树是不是二插搜索树
             bool left=true;
             if(i>0)
                 left=VerifySquenceOfBST(LeftSubSeq);
             
             //判断右子树是不是二插搜索树
             bool right=true;
             if(i<len-1)         
                 right=VerifySquenceOfBST(RightSubSeq);
            
             return left&&right;
        }
    };