二叉搜索树的数据结构-后序遍历序列

二叉搜索树的数据结构-后序遍历序列

标题: 输入整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果为true，则返回true，否则为false. 假设输入数组中的任何两个数字互不相同

分析: 通过后遍历二叉排序树的遍历，我们可以知道最后一个数字是树的根节点，而二叉搜索树的性质可以知道左节点值小于根节点值二叉排序树的遍历，右节点值大于根节点值. 递归.

/*
剑指offer面试题24
*/
#include <iostream>
using namespace std;
bool IsPostTree(int* a,int length){
    if(length <= 0){
        return false;
    }
    int root = *(a+length-1);
    int i=0;
    for(;i<length-1;i++){
        if(a[i] > root){
            break;
        }
    }
    int j=0;
    for(j=i;j<length-1;j++){
        if(a[j] < root){
            return false;
        }
    }
    bool left = true;
    if(i>0){
        left = IsPostTree(a,i);
    }
    bool right = true;
    if(j<length-1){
        right = IsPostTree(a+i,length-i-1);
    }
    return (left && right);
}
int main()
{
    int length,n;
    cin >> length;
    int a[length];
    if(length > 0){
        for(int i=0;i<length;i++){
            cin >> n;
            a[i] = n;
        }
    }
    bool result = IsPostTree(a,length);
    cout << result;
    return 0;
}

发布于2014-05-20 14: 49Ja°Read（...）评论（...）编辑

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-265145-1.html