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

二叉搜索树表示根节点的值，大于其左子树的所有节点值，但小于右子树的所有节点值。根节点的子节点也按照次规则。
如果数组是二叉搜索树的后序遍历的话，那么数组最后一个数就是该树的根节点，数组分为两个区间，前面的区间为左子树的所有值
后面区间为右子树的所有值。所以必须保证前面区间的所有值都小于根节点，后面区间的所有值都大于根节点。以此判断是否为二叉搜索树的后序遍历数组

#include<stdbool.h>
bool VerifySquenceOfBST(int* sequence, int sequenceLen ) 
{
    // write code here
    if( !sequence || sequenceLen <= 0) return false;
    
    int root = sequence[sequenceLen-1]; //得到根节点
    
    int left = 0;
    
    for( ; left < sequenceLen-1; ++left  )                //判断左子树区间的值
    {
        if( sequence[left] > root ) break;
    }
    
    int right = left;
    
    for( ; right < sequenceLen - 1; ++right )            //判断右子树区间的值
    {
        if( sequence[right] < root ) return false;
    }
 
    bool left_output = true;
    if( left > 0 )  
    {
        left_output = VerifySquenceOfBST( sequence,left );            //左子树区间也要满足条件    递归调用
    }
    
    bool right_output = true;
    
    if( left < sequenceLen-1 ) 
    {
        right_output = VerifySquenceOfBST( sequence+left,sequenceLen-left-1 );          //右子树区间也要满足条件
    }
    
    
    return left_output&&right_output;            //同时满足则true
    
}