首页 > 代码库 > 数据结构-二叉搜索树的后序遍历序列

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

2024-07-05 08:20:51   226人阅读

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回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;
}

 


联系
我们