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.
Input Specification:
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.
Output Specification:
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.
Sample Input 1:
7
8 6 5 7 10 8 11Sample Output 1:
YES
5 7 6 8 11 10 8Sample Input 2:
7
8 10 11 8 6 7 5Sample Output 2:
YES
11 8 10 7 5 6 8Sample Input 3:
7
8 6 8 5 10 9 11Sample Output 3:
NO这题也是血汗泪啊！前前后后鼓捣两个小时，其实不至于，看了题解的思路其实很好实现。
但是我纠结在我的思路里出不去了，我就想把它实现出来，最后终于折腾出来了。
其实 我的思路也很简洁，但是有一个小坑我找了好久。
具体思路是：
由于二叉排序树的中序遍历是有序的，那么二叉排序树和它的镜像树的中序遍历序列
其实就是已知序列排个序，从小到大排一下，从大到小排一下，用得到的中序序列和已知
的先序序列建树，不能建成功就说明不是。PAT 1020也用到了中序和先序序列建树的算法。
啊！赶紧去做数学了，今天刷题用的时间太多了，任务要完不成了，祝我圆满完成任务。
/********************** author: yomi date: 18.8.17 ps: **********************/ #include <iostream> #include <algorithm> using namespace std; struct node { int data; node* lchild; node* rchild; }; int pre[1500]; int post[1500]; int in[1500]; int flag = 1, cnt = 0, flag1 = 0, t = 0; int cmp(int a, int b) { return a>b; } void post_order(node* root) { if(root!=NULL){ post_order(root->lchild); post_order(root->rchild); post[cnt++] = root->data; return; } } node* create(int preL, int preR, int inL, int inR) { // if(flag == 0) // return NULL; if(preL>preR){ return NULL; } int k = -1; if(flag1){ for(int i=inR; i>=inL; i--){///坑--->我找了好久 if(in[i] == pre[preL]){ k = i; break; } } } else{ for(int i=inL; i<=inR; i++){ if(in[i] == pre[preL]){ k = i; break; } } } if(k == -1) return NULL; int numLeft = k-inL; node* root = new node; root->data = pre[preL]; root->lchild = create(preL+1, preL+numLeft, inL, k-1); root->rchild = create(preL+numLeft+1, preR, k+1, inR); t++; return root; } int main() { int n; cin >> n; flag = 1; node* root; for(int i=1; i<=n; i++){ cin >> pre[i]; in[i] = pre[i]; } sort(in+1, in+n+1); root = create(1, n, 1, n); if(t != n){ flag1 = 1; t = 0; sort(in+1, in+n+1, cmp); root = create(1, n, 1, n); //cout << t << endl; } if(t != n) cout << "NO"; else{ cout << "YES" << endl; // cout << root->data << endl; post_order(root); for(int i=0; i<cnt-1; i++){ cout << post[i] << ‘ ‘; } cout << post[cnt-1]; } return 0; } /** 7 8 6 5 7 10 8 11 Sample Output 1: YES 5 7 6 8 11 10 8 Sample Input 2: 7 8 10 11 8 6 7 5 Sample Output 2: YES 11 8 10 7 5 6 8 Sample Input 3: 7 8 6 8 5 10 9 11 **/
原文：https://www.cnblogs.com/AbsolutelyPerfect/p/9494972.html