对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式:

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例1:

1
2
7
8 6 5 7 10 8 11

输出样例1:

1
2
YES
5 7 6 8 11 10 8

输入样例2:

1
2
7
8 6 8 5 10 9 11

输出样例2:

1
NO

思路：

首先要明确 二叉搜索树 由于其本身得性质已知先序是可以写出后序遍历的

然后 假设是二叉搜索树，得到后序遍历 若长度为n，则成立，否则再判断镜面二叉搜索树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;
vector<int> post, arr;
bool flag;  //初始假设为二叉搜索树
//如果能成功转换的话就可以
void Post(int root, int end) {
  if (root > end) return;
  int i = root + 1;
  int j = end;
  //需要确定左右子树的头尾 即确定左子树的尾 和 右子树的头
  if (!flag) {
    while (i <= end && arr[i] < arr[root]) i++;   //找右子树的头
    while (j > root && arr[root] <= arr[j]) j--;   //找左子树的尾
  } else {                                        //镜像二叉
    while (i <= end && arr[root] <= arr[i]) i++;  //找右子树的头
    while (j > root && arr[j] < arr[root]) j--;    //找左子树的尾
  }

  //根据后序遍历 左右根 的顺序
  if (i - j != 1) return;
  Post(root + 1, j);
  Post(i, end);
  post.push_back(arr[root]);
}

int main() {
  int n;
   scanf("%d", &n);arr.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

  //先看看是不是二叉搜索树
  Post(0, n - 1);
  if (post.size() != n) {
    flag = true;
    post.clear();
    Post(0, n - 1);
  }
  if (post.size() == n) {
    printf("YES\n%d", post[0]);
    for (int i = 1; i < n; i++) printf(" %d", post[i]);

  } else
    cout << "NO" << endl;
}