A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.
Now given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.
译：二叉搜索树(BST)递归定义为具有以下属性的二叉树:
如果我们交换每个节点的左子树和右子树，那么得到的树被称为一个BST的镜像。现在给定一个整数键序列，您应该知道它是BST的预序遍历序列还是BST的镜像。
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.
译：每个输入文件包含一个测试用例。对于每种情况，第一行包含一个正整数N(≤1000)。然后在下一行给出N个整数键。一行中的所有数字用空格隔开。
For each test case, first print in a line YES if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or NO if not. Then if the answer is YES, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
译：对于每个测试用例，如果序列是BST的预序遍历序列或BST的镜像，则首先在一行中打印 YES，如果不是，则打印 NO。然后，如果答案是YES，则在下一行打印该树的 postorder 遍历序列。一行中的所有数字必须用空格隔开，行尾不能有多余的空格。。
7
8 6 5 7 10 8 11
YES
5 7 6 8 11 10 8
7
8 10 11 8 6 7 5
YES
11 8 10 7 5 6 8
7
8 6 8 5 10 9 11
NO
技巧如下：
#include<bits/stdc++.h>
using namespace std ;
// 排序二叉树的存储结构
struct node{
int data ; // 数据域
node* lchild ; // 指向左孩子的指针域
node* rchild ; // 指向右孩子的指针域
};
int n , t ;
string s1="" , pre="" , mpre="";
vector<int> ans ; // 存储答案的后序序列
// 创建一个新结点
node* newNode(int x){
node* root = new node ;
root -> lchild = root ->rchild = NULL ; // 新结点的左右孩子指针域均为空
root -> data = x ; // 新结点的数据域为 x
return root ; // 放回新结点
}
void insert(node* &root , int x){
if(root == NULL){
root = newNode(x) ; // 如果为空树，即插入位置
return ;
}
if(x < root -> data) insert(root -> lchild , x) ; // 说明 x 在左子树，递归左子树
else insert(root -> rchild , x) ; // 说明 x 在右子树，递归右子树
}
// 对二叉排序树先序遍历
void preorder(node* root){
if(root == NULL) return ; // 空树返回
pre += to_string(root -> data) ; // 访问当前根结点
preorder(root->lchild) ; // 访问左子树
preorder(root->rchild) ; // 访问右子树
}
// 对镜像树先序遍历
void mpreorder(node* root){
if(root == NULL) return ; // 空树返回
mpre += to_string(root -> data) ;// 访问当前根结点
mpreorder(root->rchild) ; // 访问左子树 (排序二叉树的右子树就是镜像树的左子树)
mpreorder(root->lchild) ; // 访问右子树 (排序二叉树的左子树就是镜像树的右子树)
}
// 后序遍历二叉排序树
void postorder(node* root){
if(root == NULL) return ;// 空树返回
postorder(root->lchild) ;// 访问左子树
postorder(root->rchild) ;// 访问右子树
ans.push_back(root -> data) ;// 访问当前根结点
}
// 后序遍历镜像树
void mpostorder(node* root){
if(root == NULL) return ;// 空树返回
mpostorder(root->rchild) ; // 访问左子树 (排序二叉树的右子树就是镜像树的左子树)
mpostorder(root->lchild) ; // 访问右子树 (排序二叉树的左子树就是镜像树的右子树)
ans.push_back(root -> data) ; // 访问当前根结点
}
int main(){
scanf("%d" , &n) ; // 输入结点个数 n
node* root = NULL ; // 新建根结点，初值为 NULL
for(int i = 0 ; i < n ; i ++){
scanf("%d" , &t) ; // 输入第 i 个结点的权值
insert(root , t) ; // 往排序二叉树中插入该结点
s1 += to_string(t) ; // 记录输入数据的顺序的string，便于比较
}
preorder(root) ; // 排序二叉树的先序遍历
mpreorder(root) ; // 静态树的先序遍历
if(s1 == pre ){ // 如果输入序列即为排序二叉树的先序序列
postorder(root) ;// 后序遍历排序二叉树
printf("YES\n") ;
for(int i = 0 ; i < ans.size() ; i ++) // 打印后序序列
printf("%d%c" , ans[i] , (i == ans.size() - 1)?‘\n‘:‘ ‘) ;
}else if(s1 == mpre){// 如果输入序列为镜像树的先序序列
mpostorder(root) ; // 后序遍历镜像树
printf("YES\n") ;
for(int i = 0 ; i < ans.size() ; i ++) // 打印后序序列
printf("%d%c" , ans[i] , (i == ans.size() - 1)?‘\n‘:‘ ‘) ;
}else{ // 不满足要求的序列
printf("NO\n") ;
}
return 0;
}
PAT (Advanced Level) Practice 1043 Is It a Binary Search Tree (25 分) 凌宸1642
原文：https://www.cnblogs.com/lingchen1642/p/14635178.html