二叉搜索树的后序遍历序列

示例

思路：二叉树递归

递归函数的参数包含三个信息：遍历序列，树的起点索引位置，树的重点索引位置。

对于后序遍历的二叉搜索树来讲，终点位置就是根，然后从后往前遍历找到的第一个小于终点位置的节点，就是在序列中划分左右子树的分割位置。

只要能够一直划分下去，直到递归最后是单个节点，则说明应该返回true，否则返回false。

具体步骤

• 首先对于给定列表长度为0的特殊情况返回false.
• 递归函数中返回条件为 l>=r，返回true.
• 递归函数中确定根节点为sequence[r]，然后从后往前遍历找到左右子树分割点，进行继续递归.

代码

class Solution {
public:
bool jude(vector<int>& s,int l,int r)
{
    //l==r对应的是叶子结点，l>r对应的左子树或者右子树是空树，这两种情况都是合法的二叉搜索树
    if(l>=r) return true;
    int j; 
    //right记录根节点
    int right=s[r];       
     // 找到左子树和右子树的分界点，j代表左子树的最后一个索引位置
    for(j=r;j>=l;j--)
    {
        int cur=s[j];
        if(cur<right)  break;
    }

    // 判断所谓的左子树中是否有不合法（不符合二叉搜索树）的元素
    for(int i=j;i>=l;i--){
        int cur=s[i];
        if(cur>right) return false;
    }
  return jude(s,  l,  j)&&jude(s,j+1,r-1);
}
bool VerifySquenceOfBST(vector<int> sequence) {
   if(!sequence.size()) return false;
   return jude(sequence,0,sequence.size()-1);
}
};