题目： 输入整数序列，判断该数组是不是某个二叉查找树的后续遍历结果，是返回true,不是返回false.
解： 二叉查找树中有左孩子<=父节点<右孩子，所以如果1个序列是2叉查找树的后续遍历结果的话，那么最后1个元素就是根，以数组5,7,6,9,11,10,8说明，假设它是的话，那么8就是这棵树的根，从头开始遍历直到>8的元素为止，前面的元素都属于左孩子，后面的元素除了末尾都属于右孩子，因为这是我们已经判断左孩子的节点都<=8,那么就在右孩子中遍历，如果元素有小于8的，就不满足二叉查找树性质，返回false了；如果都>8，那么继续判断左孩子和右孩子是不是二叉查找树的后续遍历，当且仅当左右孩子都是时，那么这个数组序列就返回true,否则返回false
代码:
#include<iostream> using namespace std; //判断a[begin]->a[end]是不是 bool isbt(int* a,int begin,int end) { //单节点是的 if(begin>=end) return true; else if(begin<end) { int root=a[end]; int i,j,p=begin; for(i=begin;i<end;) if(a[i]<=root) i++; else //a[i]>root即到右子树的第一个节点 break; p=i; //现在判断右子树的节点是不是都>root,如果不是的话，那么直接不是2叉查找数，如果是的话，看左右孩子 bool isnot=false; for(j=i;j<end;j++) if(a[j]<root) isnot=true; //如果正是不是 if(isnot) return false; //下面看左右孩子是不是了 bool leftis=isbt(a,begin,p-1); bool rightis=isbt(a,p,end-1); //如果左右孩子都是 if(leftis && rightis) return true; else return false; } } int main(void) { int a[]={5,7,6,9,11,10,8}; int b[]={7,4,6,5}; //bool flag=isbt(a,0,6); bool flag=isbt(b,0,3); if(flag) cout<<"是"<<endl; else cout<<"不是"<<endl; return 0; }