1.题目描述：
通过我们给出的一个后序遍历结果，找出一颗二叉树满足要求，找到了，返回true，没找到返回false
2.解法：
又是一道BST 性质和后序遍历结合的题：
首先BST我们就不过多赘语了：
BST总结
我们这道题主要考的使我们的后序遍历的性质：
我们对一个给出的后序遍历可以这么来理解：
我们把后序遍历先拆开两块：
后序遍历的划分特点
A
|B
|C (A是左子树序列，B是右子树序列，C是根节点)
每个A,B都可以继续进行上述拆分知道我们拆到单独的节点元素为止
好了，这道题我们需要的知识点已经具备齐了，剩下的我们需要的就是理解一下综合BST和后序遍历的特征了
我们可以发现，如果BST的性质中是这么说的，左子树所有的节点都比根节点小，右子树的节点都比根节点大，那么我们可以很敏锐的通过递归的性质来看出，一旦我们将后序遍历按照我们上述讲解后序遍历的划分特点的话，那么我们只要判断左子树有没有比根节点大的，有就返回false，否则继续判断，知道我们找不到任何反例的话就返回true
不想网上的其他人写的那样，我们没必要根据后序遍历构建BST，再后序遍历来判断
3.C++代码封装：
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#define N 100
using namespace std;
template<typename T>
class findBST
{
public:
findBST()
{
memset(aftorder,0,sizeof(aftorder));
num=0;
}
void prejudge()
{
if(judge(1,num)) cout<<"存在满足条件的BST"<<endl;
else cout<<"不存在满足条件的BST"<<endl;
}
bool judge(int left,int right) //递归的核心代码段，包含有后序遍历的意味在里面
{
if(left>=right) return true; //如果我们都扫到唯一一个节点的时候，还满足BST 的性质，只能说明，这个后序遍历满足BST的数的性质
int mid;
for(mid=left;mid<right;mid++) if(aftorder[mid]>aftorder[right]) break; //查找mid分割点，查找第一个比根节点大的元素
for(int i=mid+1;i<right;i++) if(aftorder[i]<aftorder[right]) return false; //开始判断
if(judge(left,mid-1)) return true;
if(judge(mid,right)) return true;
return false;
}
void set()
{
cout<<"后序遍历的长度"<<endl;
cin>>num;
cout<<"请输入后序遍历的顺序"<<endl;
for(int i=1;i<=num;i++) cin>>aftorder[i];
}
private:
T aftorder[N];
int num;
};
int main()
{
findBST<int> my;
my.set();
my.prejudge();
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1296127.html
