二叉搜索树的后序遍历序列（判绝后序遍历序列是否合法）

二叉搜索树的后序遍历序列（判断后序遍历序列是否合法）
（1）题目描述

题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

输入：

每个测试案例包括2行：

第一行为1个整数n(1<=n<=10000)，表示数组的长度。

第二行包含n个整数，表示这个数组，数组中的数的范围是[0,100000000]。

输出：

对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结果输出Yes，否则输出No

（2）程序实现       二叉搜索树的性质是：元素的左子树上的元素全部小于该元素，右子树上的元素全部大于该元素。后序遍历根节点总是在最后，所以根据后序遍历顺序可以得到根元素，并且得到根元素的左子树和右子树。假设树的后序遍历顺序为：3,7,4,6,5；可以判断出：5是根节点，3为根节点的左子树，7,4,6是根节点的右子树，但是右子树需要保证所有节点大于根节点，所以这个顺序不是二叉搜索树的后序遍历顺序。       解题思路：在标识出左右子树时，遍历右子树，发现右子树中的元素小于其父节点，则顺序为错误的。（PS：这种解法还需要优化，目前想到的办法是存储两个变量，标识子树中元素的最大值和最小值，还需要优化）

#include <iostream> using namespace std; bool IsValid(int *data, int n, int left, int right){     if(left>=right)         return true;     int mid = 0;     int root = data[right];      //标识左子树，右子树的分割位置     for(mid = left; mid<right,data[mid]<root; ++mid)         ;      //判断子树是否合法     for(int i=mid; i<right; ++i)     {         if(data[i]<root)             return false;     }     if(!IsValid(data, n, left, mid-1))         return false;     if(!IsValid(data, n, mid+1, right))         return false;     return true;} int main(){    int n;    while(cin>>n)    {        int *data = new int[n];        for(int i=0; i<n; ++i)            cin>>data[i];        if(!IsValid(data, n, 0, n-1))            cout<<"No"<<endl;        else            cout<<"Yes"<<endl;                delete[] data;    }}

查看更多 下一篇