题目描述
对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。
现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。
输入
输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。
输出
输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。
输入样例1
7 8 6 5 7 10 8 11
输出样例1
YES 5 7 6 8 11 10 8
AC代码
代码语言：javascript复制#include <iostream>
#include<vector>
using namespace std;
vector<int>data;
struct Node {
int data;
Node *left = NULL;
Node *right = NULL;
};
class BST {
Node *root = NULL;
vector<int>pre,post,mirror;
public:
void Insert(int &data) {
Node *newOne = new Node();
newOne->data = data;
if (root == NULL) {
root = newOne;
return;
}
Node *current = root;
while (current) {
if (current->data > data) {
if (current->left)
current = current->left;
else {
current->left = newOne;
return;
}
} else {
if (current->right)
current = current->right;
else {
current->right = newOne;
return;
}
}
}
}
void Preorder(Node *current) {
if (current == NULL)
return;
pre.push_back(current->data);
Preorder(current->left);
Preorder(current->right);
}
void mirrorPreorder(Node *current) {
if (current == NULL)
return;
mirror.push_back(current->data);
mirrorPreorder(current->right);
mirrorPreorder(current->left);
}
void Postorder(Node *current) {
if (current == NULL)
return;
Postorder(current->left);
Postorder(current->right);
post.push_back(current->data);
}
void Show(vector<int>&temp) {
for(int i=0;i<temp.size()-1;i )
cout<<temp[i]<<' ';
cout<<temp[temp.size()-1]<< endl;
}
bool Check(vector<int>&a,vector<int>&b){
for(int i=0;i<a.size();i )
if(a[i]!=b[i])
return false;
return true;
}
void Show(){
Postorder(root);
Preorder(root);
mirrorPreorder(root);
if(Check(data,pre)|| Check(data,mirror)){
cout<<"YES"<<endl;
Show(post);
}else
cout<<"NO"<<endl;
}
};
int main() {
int n, temp;
BST test;
cin >> n;
while (n--) {
cin >> temp;
data.push_back(temp);
test.Insert(temp);
}
test.Show();
return 0;
}
