题目1367：二叉搜索树的后序遍历序列
时间限制：1 秒内存限制：32 兆特殊判题：否提交：1359解决：684
题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
输入：
每个测试案例包括2行：
第一行为1个整数n(1<=n<=10000)，表示数组的长度。
第二行包含n个整数，表示这个数组，数组中的数的范围是[0,100000000]。
输出：
对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结果输出Yes，否则输出No。
样例输入：
7
5 7 6 9 11 10 8
4
7 4 6 5
样例输出：
Yes
No

#include <iostream>
#include<stdio.h>
using namespace std;
//最后的节点为根节点，比根节点小的位于左子树，大的位于右子树
bool VerifySquenceOfBST(int sequence[],int length){
    if(sequence==NULL||length<=0){
        return false;
    }
    int root = sequence[length-1];
    int i=0;
    for(;i<length-1;i++){
        if(sequence[i]>root){
            break;
        }
    }
    int j=i;
    for(;j<length-1;j++){
        if(sequence[j]<root){
            return false;
        }
    }
    //左子树为空时，是搜索树
    bool left = true;
    if(i>0){
        left = VerifySquenceOfBST(sequence,i);
    }
    bool right = true;
    if(i<length-1){
        right = VerifySquenceOfBST(sequence+i,length-i-1);
    }
    return left&&right;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int* sequence = new int[n];
        for(int i=0;i<n;i++){
            scanf("%d",&sequence[i]);
        }
        if(VerifySquenceOfBST(sequence,n)){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
    return 0;
}

剑指offer系列源码-二叉搜索树的后序遍历序列