距离PAT考试还有11天最重要的是做透每一题
(1)思路
首先根据前序数列判断是否有左右子树找到
然后根据bst的性质判断左子树是否都小于根,右子树都大于等于根
或者左子树是否都大于等于根,右子树都小于根
然后再前序转后序
#include <cstdio> #include <vector> using namespace std; int n; vector<int> pv; vector<int> postov; bool isbst(int root,int left,int right) { //左右子树的位置 if(left == right) return true; if(pv[root] <= pv[root+1]) {//左子树不存在 bool ns=true; for(int i=root+1;i<=right;i++) { if(pv[root] > pv[i]) ns=false; } return ns&&isbst(root+1,root+1,right); } else {//左子树存在 int ri=-1; for(int i=root+1;i<=right;i++) { if(pv[root] <= pv[i]) { ri=i; break; } } if(ri == -1) {//右子树不存在 bool ns=true; for(int i=root+1;i<=right;i++) { if(pv[root] <= pv[i]) ns=false; } return ns&&isbst(root+1,root+1,right); } else { //右子树存在 bool ns=true; for(int i=root+1;i<ri;i++) { if(pv[root] <= pv[i]) ns=false; } for(int i=ri;i<=right;i++) { if(pv[root] > pv[i]) ns=false; } return ns && isbst(root+1,root+1,ri) && isbst(ri,ri,right); } } } bool isrbst(int root,int left,int right) { //左右子树的位置 if(left == right) return true; if(pv[root] > pv[root+1]) {//左子树不存在 bool ns=true; for(int i=root+1;i<=right;i++) { if(pv[root] <= pv[i]) ns=false; } return ns&&isrbst(root+1,root+1,right); } else {//左子树存在 int ri=-1; for(int i=root+1;i<=right;i++) { if(pv[root] > pv[i]) { ri=i; break; } } if(ri == -1) {//右子树不存在 bool ns=true; for(int i=root+1;i<=right;i++) { if(pv[root] > pv[i]) ns=false; } return ns&&isrbst(root+1,root+1,right); } else { //右子树存在 bool ns=true; for(int i=root+1;i<ri;i++) { if(pv[root] > pv[i]) ns=false; } for(int i=ri;i<=right;i++) { if(pv[root] <= pv[i]) ns=false; } return ns && isrbst(root+1,root+1,ri) && isrbst(ri,ri,right); } } } void posto(int root,int l,int r) { if(l > r) return; if(l == r) { postov.push_back(pv[root]); return; } int ri=-1; for(int i=root+1;i<=r;i++) { if((pv[i] >= pv[root] && pv[i-1] < pv[root]) || (pv[i] < pv[root] && pv[i-1] >= pv[root])) ri=i; } if(ri == -1) { posto(root+1,root+1,r); postov.push_back(pv[root]); } else { posto(root+1,root+1,ri-1); posto(ri,ri,r); postov.push_back(pv[root]); } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { int v; scanf("%d",&v); pv.push_back(v); } bool t1=isbst(0,0,n-1); bool t2=isrbst(0,0,n-1); if(t1 || t2) { printf("YES "); posto(0,0,n-1); for(int i=0;i<n;i++) { i == 0? printf("%d",postov[i]):printf(" %d",postov[i]); } } else { printf("NO"); } }
这里也可以把isbst和isrbst 写在一个函数里0.0
(2)
思路就是按照bst和rbst性质，试着得到post如果两次post都没有n个元素这不是bst也不是rbst
#include <cstdio> #include <vector> using namespace std; bool isM; vector<int> pre,post; int n; void getpost(int l,int r) { if(l > r) return; if(l == r) { post.push_back(pre[l]); return; } //l 到 r至少有2个节点 int i=l+1; int j=r; if(isM == false) {//得到子树的位置,i为右子树起始,j为右子树树结束 while(i <= r && pre[i] < pre[l]) i++; while(j > l && pre[j] >= pre[l]) j--; } else { while(i <= r && pre[i] >= pre[l]) i++; while(i > l && pre[j] < pre[l]) j--; } //i,j有如下情况,边界情况 //i可能超过r , 此时j为r 满足i-j ==1 //j可能等于l,此时也满足i-j ==1 //非边界的一般情况也有该性质成立 //i-j!=1 这时必然不满足bst性质退出 if(i-j != 1) return; //继续考虑边界情况,i超过r时意味着只有左子树,2式进入后会直接退出 //j等于l时,意味着没有右子树,1时进入后会直接退出 //一般的情况1 2也可以发现是正确的 getpost(l+1,j); //1 getpost(i,r); //2 post.push_back(pre[l]); return; } int main() { isM=false; scanf("%d",&n); pre.resize(n); for(int i=0;i<n;i++) { scanf("%d",&pre[i]); } getpost(0,n-1); if(post.size() != n) {//判断是否是镜像 isM=true; post.clear(); getpost(0,n-1); } if(post.size() == n) {//有n个数代表是bst或rbst printf("YES "); for(int i=0;i<n;i++) { i==0? printf("%d",post[i]):printf(" %d",post[i]); } return 0; } printf("NO"); return 0; }
