【二叉搜索树】PAT-天梯赛- L2-004. 这是二叉搜索树吗？

大致题意：一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

其左子树中所有结点的键值小于该结点的键值；

其右子树中所有结点的键值大于等于该结点的键值；

其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

大致思路：~~以上给出的是二叉搜索树的概念，该树的镜像其实仔细一想无非就是一棵任何节点的右子树严格小于该节点的值，并且相当于建图的时候就是反着反向按照二叉搜索树的结构来存储的。

于是乎：就按照二叉搜索树的结构建树一次，图上给的正巧就是先序遍历，就先序建图一次！万一是镜像了还要考虑，再按照镜像左右子树正好颠倒的方式来进行二次建图！两次建图后再分别先序遍历——若结果与题目给的一直就符合，后序再次遍历就是结果！若两个都不符合，则输出“NO”！

最后总结，二叉树搜索树的结构确定了一点，先序遍历的结果一定是唯一的！根据先序遍历的结构构造的二叉树也是唯一的！

——————————————最后自己动手画画，举几个简单的栗子来证明一下自己的猜测，代码里适当地添加了注释了，看不懂了就再点开看看————————————————

AC代码：

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<math.h>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<set>
  8 #include<string>
  9 #include<map>
 10 #define maxn 400000
 11 #define  inf 0x3f3f3f3f
 12 using namespace std;
 13 #define N 1008
 14 typedef struct Bitnode{
 15   int data;
 16   struct Bitnode *lchild;
 17   struct Bitnode *rchild;
 18 }Abitnode,*bitree;
 19 int n,n2,n3;
 20 int num[N],num2[N],num3[N];
 21 int n4,ans[N];//存储答案
 22 void insertbitree(bitree *T,int num){
 23     if(*T==NULL){
 24          *T=(bitree)malloc(sizeof(Abitnode));
 25         (*T)->data=num;
 26         (*T)->lchild=NULL;
 27         (*T)->rchild=NULL;
 28         return ;
 29     }
 30     if((*T)->data > num){
 31         insertbitree(&(*T)->lchild,num);//左子树严格小于根节点的值
 32     }else{
 33         insertbitree(&(*T)->rchild,num);
 34     }
 35 }
 36 void fact2(bitree *T){//按照先序遍历，二叉搜索树：左子树严格小
 37     if((*T)!=NULL){
 38         num2[++n2]=(*T)->data;
 39         fact2(&(*T)->lchild);
 40         fact2(&(*T)->rchild);
 41     }
 42     return ;
 43 }
 44 void fact3(bitree *T){//按照先序遍历，二叉搜索树的镜像：右子树严格小
 45     if((*T)!=NULL){
 46         num3[++n3]=(*T)->data;
 47         fact3(&(*T)->rchild);
 48         fact3(&(*T)->lchild);
 49     }
 50     return ;
 51 }
 52 bool judge(int a[],int b[]){
 53     for(int i=1;i<=n;i++)
 54         if(a[i]!=b[i])
 55             return false;
 56     return true;
 57 }
 58 void post_print2(bitree *T){//后续遍历输出二叉搜索树,存到ans中
 59     if(*T!=NULL){
 60         post_print2(&(*T)->lchild);
 61         post_print2(&(*T)->rchild);
 62         ans[++n4]=((*T)->data);
 63     }
 64 }
 65 void post_print3(bitree *T){//后续遍历输出镜像，存到ans中
 66     if(*T!=NULL){
 67         post_print3(&(*T)->rchild);
 68         post_print3(&(*T)->lchild);
 69         ans[++n4]=((*T)->data);
 70     }
 71 }
 72 void print_ans(){
 73     printf("YES
");
 74     for(int i=1;i<=n;i++){
 75         if(i==n)
 76             printf("%d
",ans[i]);
 77         else
 78             printf("%d ",ans[i]);
 79     }
 80     return ;
 81 }
 82 int main(){
 83     bitree T;
 84     while(scanf("%d",&n)!=EOF){//既然是前序遍历，第一个点铁定是根节点
 85         T=NULL;
 86         for(int i=1;i<=n;i++){//按照前序遍历的顺序
 87             scanf("%d",&num[i]);
 88             insertbitree(&T,num[i]);
 89         }
 90         n2=0;
 91         fact2(&T);
 92         n3=0;
 93         fact3(&T);
 94         n4=0;
 95         if(judge(num,num2)){//如果是二叉搜索树
 96             post_print2(&T);
 97             print_ans();
 98         }
 99         else if(judge(num,num3)){//如果是二叉搜索树的镜像
100             post_print3(&T);
101             print_ans();
102         }
103         else{
104             printf("NO
");
105         }
106     }
107     return 0;
108 }
109 /*
110 题目思路：1、正常按二叉树进行建立，然后按照规则进行搜索——OK！；
111           2、404！
112 */

View Code