对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。
现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。
判断搜索二叉树:先判断给出的数组是不是前序(由建立的后序判断）：需要注意的是；不知这是否为“普通二叉搜索树”还是镜像二叉搜索树。所以先得建立bool Minoor；然后再根据情况依次建立左右子树。
<关键点>根据建立的后序判断其长度是否为输入的长度n，若不是再回过去判断镜像二叉搜索树是否满足（判断条件同前）；
代码:
/* @输入的序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列， *如果是,则输出对应二叉树的后序遍历序列 */ #include <iostream> #include <algorithm> #include <cstdlib> #include <vector> using namespace std; typedef struct Tnode{ int data; struct Tnode *left; struct Tnode *right; }Tnode,*Three; bool flag = true; vector<int>pos; void post_tree(int front,int end,int pre[]){ if(end>=front){ int root = pre[front]; int a = front+1; int b = end; if(flag){ while(root>pre[a]&&a<=b){ a++; } while(root<=pre[b]&&b>=a){ b--; } } else{ while(root<=pre[a]&&a<=b){ a++; } while(root>pre[b]&&b>=a){ b--; } } /* 思路:因为搜索树有根节点左侧的值都比根节点小,右侧值都比根节点大的特性 前序遍历：根->左->右顺序。所以按给定数组第一个为根节点,从根节点此后找比根节点小 的元素。直到碰到大于根节点元素为止。此步骤找到的即为树的左部分.同理从数组的最后往前推 找出比根节点大的。这部分为树的右部分。至此将树划分完.若通过对其后序搜索后元素的数量 与输入的数量不符。则为非二叉搜索树或某镜像二叉搜索树的前序遍历序列。 例子:8,4,5,6,9,7,10,12那么左树为4,5,6,9,7右树为9,7,10,12显然9,7被重复计算了,结果是否定的. */ /*实现后序化*/ //因为搜索树有特性 post_tree(front+1,b,pre); //类前序处理 post_tree(a,end,pre); //类后序处理 pos.push_back(root); //根处理 } } int main(){ int n; cin>>n; int pre[1000]; for(int i = 0;i<n;i++){ cin>>pre[i]; } post_tree(0,n-1,pre); if(pos.size()!=n){ //普通二叉搜索树不满足 flag = false; pos.clear(); //清空之前的pos数组 post_tree(0,n-1,pre); //回过去检验镜像二叉搜索树是否满足 } if(pos.size()==n){ cout<<"YES"<<endl; cout<<pos[0]; for(int j = 1;j<pos.size();j++){ cout<<" "<<pos[j]; } } else{ cout<<"NO"<<endl; } return 0; }