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

• 其左子树中所有结点的键值小于该结点的键值；
• 其右子树中所有结点的键值大于等于该结点的键值；
• 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：
输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

7
8 6 5 7 10 8 11

输出样例 1：

YES
5 7 6 8 11 10 8

输入样例 2：

7
8 10 11 8 6 7 5

输出样例 2：

YES
11 8 10 7 5 6 8

输入样例 3：

7
8 6 8 5 10 9 11

输出样例 3：

NO

分析
因为前序遍历是根左右，所以在插入某个孩子节点时，它的父节点肯定已经被插入了，又由于搜索树的限制关系（小的左边，大的右边），所以可以确定一棵唯一的二叉搜索树，然后对其进行两种不同的前序遍历，再分别与题目所给的序列比较即可。
代码

//                              _ooOoo_
//                             o8888888o
//                             88" . "88
//                             (| -_- |)
//                              O\ = /O
//                           ____/`---'\____
//                        .   ' \| |// `.
//                         / \||| : |||// \
//                        / _||||| -:- |||||- \
//                         | | \\ - /// | |
//                       | \_| ''\---/'' | |
//                        \ .-\__ `-` ___/-. /
//                    ___`. .' /--.--\ `. . __
//                  ."" '< `.___\_<|>_/___.' >'"".
//                 | | : `- \`.;`\ _ /`;.`/ - ` : | |
//                    \ \ `-. \_ __\ /__ _/ .-` / /
//           ======`-.____`-.___\_____/___.-`____.-'======
//                              `=---='
//
//           .............................................
//                   佛祖保佑     一发AC     永无BUG
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
struct node {
    node *l, *r;
    int data;
};
//s1为正常前序遍历，s2为左右儿子颠倒的前序遍历，s为输入序列
int s1[maxn], s2[maxn], s[maxn], n, cnt;
vector<int> ans;
node *build(node *root, int x) {
    if (root == NULL) {
        //到达最底部，创建新节点，并赋值
        root = new node;
        root->l = root->r = NULL;
        root->data = x;
    } else if (x < root->data) {
        //x小于当前节点，说明x在root的左半边，向左递归
        root->l = build(root->l, x);
    } else {
        root->r = build(root->r, x);
    }
    return root;
}
//正常前序遍历
void qian1(node *root) {
    if (root == NULL) return;
    s1[cnt++] = root->data;
    qian1(root->l);
    qian1(root->r);
}
//左右颠倒的前序
void qian2(node *root) {
    if (root == NULL) return;
    s2[cnt++] = root->data;
    qian2(root->r);
    qian2(root->l);
}
//正常后序
void hou1(node *root) {
    if (root == NULL) return;
    hou1(root->l);
    hou1(root->r);
    ans.push_back(root->data);
}
//左右颠倒的后序
void hou2(node *root) {
    if (root == NULL) return;
    hou2(root->r);
    hou2(root->l);
    ans.push_back(root->data);
}
//比较两个序列是否完全相同
bool judge(int *a) {
    for (int i = 0; i < n; i++) {
        if (a[i] != s[i]) return 0;
    }
    return 1;
}
int main(int argc, char const *argv[]) {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    node *root = NULL;
    for (int i = 0; i < n; i++) {
        root = build(root, s[i]);
    }
    qian1(root);
    cnt = 0;
    qian2(root);
    if (judge(s1)) {//说明所给序列是二叉搜索树的前序遍历
        hou1(root);
        puts("YES");
        for (int i = 0; i < n; i++)
            printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
    } else if (judge(s2)) {//是镜像的前序遍历
        puts("YES");
        hou2(root);
        for (int i = 0; i < n; i++)
            printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
    } else {//不是二叉搜索树输出-1
        puts("NO");
    }
    return 0;
}