河北大学程序设计训练营

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

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

输入格式:

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

输出格式:

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

输入样例1:

7
8 6 5 7 10 8 11

输出样例1:

YES
5 7 6 8 11 10 8

输入样例2:

7
8 6 8 5 10 9 11

输出样例2:

NO

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4+10;
int n, w[N], f, F = 1;

bool dfs(int l,int r)
{
	if(l > r) return true;
	int i = l + 1;
	for(; i <= r; ++i) 
		if(F == 1 && w[i] >= w[l] || (F == -1 && w[i] > w[l])) break; // 找到左右子树分割的标记 
	for(int j = i; j <= r; ++j) if(w[j] < w[l]) return false;
	return dfs(l + 1, i - 1) && dfs(i, r); //递归处理 
}

void post(int l,int r)//后续遍历
{
	if(l > r) return;
	int i = l + 1;
	for(; i <= r; ++i) 
		if(F == 1 && w[i] >= w[l] || (F == -1 && w[i] > w[l])) break;// 找到左右子树分割的标记 
	post(l + 1, i - 1); post(i, r); // 后序输出 
	if(f) cout << ' ';
	cout << w[l] * F; f = true;
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++ i) cin >> w[i];
	
	if(n >= 2 && w[2] > w[1])//镜像二叉搜索树的情况
	{
		for(int i = 1; i <= n; ++i) w[i] *= -1;
		F = -1;//状态标记
	}
	if(!dfs(1, n)) cout << "NO" << endl;
	else
	{
		cout << "YES" << endl;
		post(1, n);
	}
}