题目粗心：
现给定一颗N个结点的树,判断该树是否是二叉查找树或者镜像二叉查找树,如果是输入YES并输入该树的后序遍历,否则输入NO
算法思路：
咱们首先通过给定的N个结点间接构建一个二叉查找树，而后再取得其先序遍历序列和镜像先序遍历序列，别离判断是否和输出的序列相等，如果输出的序列是先序遍历序列，那么就输入YES并取得其后序遍历序列进行输入，如果输出序列是镜像先序遍历序列，那么就输入YES并取得镜像后序遍历序列进行输入，如果都不是，就输入NO。
构建二叉查找树：
这里采纳间接模仿手工构建二叉查找树的过程，首先是依据插入的数据值，新建一个叶子结点，而后从根节点进行查找，如果根节点为空，阐明曾经找到插入地位，将根结点赋值为以后叶子结点即可，如果根节点的数据值小于叶子结点数据值，递归向左子树插入该结点，否则递归向右子树插入该结点。代码如下：
struct Node{ int data; struct Node* left; struct Node* right;};// 创立结点 Node* newNode(int data){ Node* node = new Node(); node->data = data; node->left = node->right = nullptr; return node;}// 插入结点到root中 void insert(Node* &root,int data){ if(root==nullptr){ // 查找到插入地位 root = newNode(data); return; } if(root->data>data){ // 在左子树中查找插入地位 insert(root->left,data); }else{ // 在右子树中查找插入地位 insert(root->right,data); }}// 建树 for(int i=0;i<N;++i){ scanf("%d",&num[i]); insert(root,num[i]);}留神点：
- 1、当输出序列为镜像先序查找树的时候，其后序序列为镜像后序序列，样例2就是该状况。
提交后果：
AC代码：
#include<cstdio>#include<vector>using namespace std;struct Node{ int data; struct Node* left; struct Node* right;};int N;int num[1001];// 存储输出序列vector<int> pre,mirrorPre,post,postMirror;// 先序，先序镜像先序，后序序列 ,后序镜像序列 // 创立结点 Node* newNode(int data){ Node* node = new Node(); node->data = data; node->left = node->right = nullptr; return node;}// 插入结点到root中 void insert(Node* &root,int data){ if(root==nullptr){ // 查找到插入地位 root = newNode(data); return; } if(root->data>data){ // 在左子树中查找插入地位 insert(root->left,data); }else{ // 在右子树中查找插入地位 insert(root->right,data); }}void preTraverse(Node* root){ if(root==nullptr) return; pre.push_back(root->data); preTraverse(root->left); preTraverse(root->right);}void preMirrotTraverse(Node* root){ if(root==nullptr) return; mirrorPre.push_back(root->data); preMirrotTraverse(root->right); preMirrotTraverse(root->left);}void postTraverse(Node* root){ if(root==nullptr) return; postTraverse(root->left); postTraverse(root->right); post.push_back(root->data);}void postMirrorTraverse(Node* root){ if(root==nullptr) return; postMirrorTraverse(root->right); postMirrorTraverse(root->left); postMirror.push_back(root->data);}// 判断输出序列是否是先序序列bool isPre(){ for(int i=0;i<N;++i){ if(pre[i]!=num[i]){ return false; } } return true;}// 判断输出序列是否是先序镜像序列bool isPreMirror(){ for(int i=0;i<N;++i){ if(mirrorPre[i]!=num[i]){ return false; } } return true;}int main(){ scanf("%d",&N); Node* root = nullptr; // 建树 for(int i=0;i<N;++i){ scanf("%d",&num[i]); insert(root,num[i]); } preTraverse(root); preMirrotTraverse(root); if(isPre()){ // 是先序序列 printf("YES\n"); postTraverse(root); for(int i=0;i<N;++i){ printf("%d",post[i]); if(i<N-1) printf(" "); } }else if(isPreMirror()){ // 是先序镜像序列 printf("YES\n"); postMirrorTraverse(root); for(int i=0;i<N;++i){ printf("%d",postMirror[i]); if(i<N-1) printf(" "); } }else { printf("NO"); } return 0;}在这里再给出间接建设BST和镜像BST的写法
#include<cstdio>#include<cstring>#include<vector>#include<iostream>using namespace std;/*题目要求:现给定一颗N个结点的树,判断该树是否是二叉查找树或者镜像二叉查找树,如果是输入YES并输入该树的后序遍历,否则输入NO 算法思路:因为得输入对应的后序遍历序列,那么就得构建这颗树了,因为有可能有2种合乎题意的树,咱们采纳2次先判断再建设树的形式.1.首先咱们先判断该树是否是BST：这里采纳的是利用先序遍历序列构建BST的过程判断是否是BST的,在以后递归体中,咱们用index保留第一个大于等于根节点的地位,因为根节点前面到index地位都小于根节点,所以只需判断前面index到完结地位是否满足BST的定义就好,也就是说如果右子树中有小于根节点的结点,那么让flag=false(flag是用来判断该树是否是BST的标记),并且return进行递归,如果右子树结点均合乎定义则进行左子树和右子树的递归即可2.如果该树是BST,就构建BST,构建BST树的过程和判断极为类似,咱们在进入递归的时候首先初始化根节点Node* root = new Node;root->data = pre[preL];同样的咱们用index保留第一个大于等于根节点的地位,区间[preL+1,index-1]就是左子树,区间[index,preR]就是右子树,而后顺次构建左子树root->left = create(preL+1,index-1),右子树root->right = create(index,preR),最初返回根结点root即可3.如果该树不是BST,就判断是否是镜像BST,这里只需将index改为保留第一个小于根节点的地位即可,而后在右子树中有大于等于根节点的结点,如果有,那么让flag=false，并且return,如果右子树结点均合乎定义则进行左子树和右子树的递归即可4.如果是镜像BST,则构建镜像BST树,这里与构建BST惟一的区别就是找到第一个小于根节点的地位index,而后左右区间均一样,递归建设树即可5.如果都不是则输入NO6.最初得记得输入后序序列postOrder */const int maxn = 1001;//最多结点数目 struct Node{ int data; Node* left; Node* right;}node[maxn];int pre[maxn];//前序和后序序列 int n;//结点个数 void isBST(int preL,int preR,bool &flag){//依据先序遍历判断该树是否是BST if(preL>preR) return; int index;//保留第一个大于等于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]>=pre[preL]){ break; } } for(int i=index;i<=preR;++i){ if(pre[i]<pre[preL]){//右子树中有小于根节点的结点 flag = false; return; } } isBST(preL+1,index-1,flag); isBST(index,preR,flag);}void isMirrorBST(int preL,int preR,bool &flag){//依据先序遍历判断该树是否是镜像BST if(preL>preR) return; int index;//保留第一个小于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]<pre[preL]){ break; } } for(int i=index;i<=preR;++i){ if(pre[i]>=pre[preL]){//右子树中有大于等于根节点的结点 flag = false; return; } } isMirrorBST(preL+1,index-1,flag); isMirrorBST(index,preR,flag);}Node* create(int preL,int preR){//依据先序遍历建设BST if(preL>preR) return NULL; Node* root = new Node; root->data = pre[preL]; root->left = root->right = NULL; int index;//保留第一个大于等于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]>=root->data){ break; } } root->left = create(preL+1,index-1); root->right = create(index,preR); return root;}Node* createMirror(int preL,int preR){//依据先序遍历建设镜像BST if(preL>preR) return NULL; Node* root = new Node; root->data = pre[preL]; root->left = root->right = NULL; int index;//保留第一个小于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]<root->data){ break; } } root->left = createMirror(preL+1,index-1); root->right = createMirror(index,preR); return root;}int num = 0;//用来统计输入节点个数并管制输入空格 void postOrder(Node *root){//后序遍历二叉树,并输入后序遍历序列 if(root==NULL) return; postOrder(root->left); postOrder(root->right); printf("%d",root->data); if(num<n-1) printf(" "); ++num; }int main(){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d",&pre[i]); } bool flag1 = true; bool flag2 = true; isBST(0,n-1,flag1); isMirrorBST(0,n-1,flag2); if(flag1||flag2){ printf("YES\n"); Node *root; if(flag1){//阐明是BST root = create(0,n-1); }else{ root = createMirror(0,n-1); } postOrder(root); }else{ printf("NO\n"); } return 0;}