面试题 24

1 题目描述

二叉搜索树的后续遍历序列：输入一个整数数组，判断数组是不是某二叉搜索树的后序遍历的结果，如果是则返回 true，否则返回 false，假设输入的数组的任意两个数字互不相同。

2 解法描述

1. 二叉搜索树，父节点大于左孩子节点，小于右孩子节点
2. 后序遍历的最后一个节点为当前树的根节点
3. 将后序遍历序列与根节点进行比较，小于根节点的序列为左子树，大于根节点的序列为右子树。
4. 然后以同样方法递归左子树和右子树

3 C 语言实现

#include<stdio.h>
int verifySquenceOfBST(int *squence,int len){
    //异常数据判断
    if(squence==NULL||len<=0) return 0;
    int rootdata=squence[len-1];
    int i;
    int index;
    int left=1;
    int right=1;
    //如果当前搜索子树只有一个节点，那么肯定满足二叉搜索树的定义
    if(squence!=NULL&&len==1) return 1;
    //后续遍历序列与根节点进行比较，查找左子树和右子树的分界点
    for(i=0;i<len;i++){
        if(*(squence+i)>rootdata){
            break;
        }
    }
    index=i;
    //若右子树中出现了比根节点小的元素，不满足二叉搜索树的定义，直接返回
    for(i=index+1;i<len-1;i++){
        if(*(squence+i)<rootdata){
            return 0;
        }
    }
    //递归检查左子树
    if(index>0){
        left=verifySquenceOfBST(squence,index);
    }
    //递归检查右子树
    if(index<len){
        right=verifySquenceOfBST(squence+index,len-index-1);
    }
    //返回结果
    return (left&right);
}
void main(){
    int squenece[]={5,7,6,9,11,10,8};
    printf("%d",verifySquenceOfBST(squenece,7));
    printf("\n");
    int squenece2[]={5,7,6,11,8,10,9};
    printf("%d",verifySquenceOfBST(squenece2,7));
    printf("\n");
    int squenece3[]={1};
    printf("%d",verifySquenceOfBST(squenece3,1));
    printf("\n");
    printf("%d",verifySquenceOfBST(NULL,0));
    printf("\n");
    int squenece4[]={1,4,2,3};
    printf("%d",verifySquenceOfBST(squenece4,4));
}