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.
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.
7 8 6 5 7 10 8 11
YES 5 7 6 8 11 10 8
//全是套路==
#include <cstdio>
#include <vector>
using namespace std;
struct Node{
int value;
Node *left, *right;
};
void Insert(Node* &root, int data){
if(root == NULL){
root = new Node;
root -> value = data;
root -> left = NULL;
root -> right = NULL;
return;
}
if(data < root->value) Insert(root->left, data);
else Insert(root->right, data);
}
void PreOrder(Node* root, vector<int>& v){
if(root == NULL) return;
v.push_back(root->value);
PreOrder(root->left, v);
PreOrder(root->right, v);
}
void PreMirrorOrder(Node* root, vector<int>& v){
if(root == NULL) return;
v.push_back(root->value);
PreMirrorOrder(root->right, v);
PreMirrorOrder(root->left, v);
}
void PostOrder(Node* root, vector<int>& v){
if(root == NULL) return;
PostOrder(root->left, v);
PostOrder(root->right, v);
v.push_back(root->value);
}
void PostMirrorOrder(Node* root, vector<int>& v){
if(root == NULL) return;
PostMirrorOrder(root->right, v);
PostMirrorOrder(root->left, v);
v.push_back(root->value);
}
int main(){
int n;
Node* s = NULL;
scanf("%d", &n);
vector<int> num, pre, preM, post, postM;
for(int i=0; i<n; i++){
int data;
scanf("%d", &data);
num.push_back(data);
Insert(s, data);
}
PreOrder(s, pre);
if(num == pre){
PostOrder(s, post);
printf("YES\n");
for(unsigned int i=0; i<post.size(); i++){
printf("%d", post[i]);
if(i < post.size()-1) printf(" ");
}
}
else{
PreMirrorOrder(s, preM);
if(num == preM){
PostMirrorOrder(s, postM);
printf("YES\n");
for(unsigned int i=0; i<postM.size(); i++){
printf("%d", postM[i]);
if(i < postM.size()-1) printf(" ");
}
}
else printf("NO\n");
}
return 0;
} 
#include <iostream>
using namespace std;
struct Node{ int val; Node *left,*right;
}a[1004];
bool first;
int n;
Node *make1(Node *a, int &now, Node *p1, Node *p2){ if(now >= n) return 0; Node *root = 0; if(((p1==0) || (a[now].val<p1->val)) && ((p2==0) || (a[now].val>=p2->val))) { root = a + now; now++; root->left = make1(a, now, root, p2); root->right = make1(a, now, p1, root); } return root;
}
Node *make2(Node *a, int &now, Node *p1, Node *p2)
{ if(now >= n) return 0; Node *root = 0; if(((p1==0) || (a[now].val>=p1->val)) && ((p2==0) || (a[now].val<p2->val))) { root = a + now; now++; root->left = make2(a, now, root, p2); root->right = make2(a, now, p1, root); } return root;
}
void DFS(Node *root)
{ if(root) { DFS(root->left); DFS(root->right); if(first) first = false; else cout<<" "; cout<<root->val; }
}
int main()
{ cin>>n; for(int i=0;i<n;i++) { cin>>a[i].val; a[i].left = a[i].right = 0; } int now; Node *root = make1(a, now=0, 0, 0); if(now < n) root = make2(a, now=0, 0, 0); if(now >= n) { cout<<"YES"<<endl; first = true; DFS(root); cout<<""; }else cout<<"NO"; return 0;
} 
#include <iostream>
using namespace std;
#define MAX 10000
int N, a[MAX], cnt = 0;
bool res1 = true, res2 = true;
typedef struct Node {
struct Node* lChild, * rChild;
int data;
}Node;
Node* T1 = NULL, *T2 = NULL;
Node* Search(Node* x, int e, Node*& _hot, bool mir) {
while (x) {
_hot = x;
if (!mir && e < x->data || mir && e >= x->data)x = x->lChild;
else x = x->rChild;
}
return x;
}
bool Insert(Node*& T, int e,bool mir) {
Node* _hot = NULL;
Node* x = Search(T, e, _hot, mir);
x = new Node; x->data = e;
x->lChild = x->rChild = NULL;
if (_hot) {
if (!mir && e < _hot->data || mir && e >= _hot->data)
_hot->lChild = x;
else _hot->rChild = x;
}
if (!T)T = x; return true;
}
void preorderCheck(Node*& T, bool& res) {
if (!T)return;
if (T->data != a[cnt++])res = false;
preorderCheck(T->lChild, res);
preorderCheck(T->rChild, res);
}
void postorderPrint(Node*& T) {
if (!T)return;
postorderPrint(T->lChild);
postorderPrint(T->rChild);
cout << T->data; if (cnt++ < N)cout << " ";
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i) {
cin >> a[i];
Insert(T1, a[i], false);
Insert(T2, a[i], true);
}
preorderCheck(T1, res1); cnt = 0;
preorderCheck(T2, res2); cnt = 0;
if (!res1 && !res2)cout << "NO";
else {
cout << "YES" << endl;
if (res1)postorderPrint(T1);
else if (res2)postorderPrint(T2);
}
return 0;
} 
#include<stdio.h>
#include<vector>
using namespace std;
int preorder[1000];
vector<int> postorder;
bool checkBST(int start, int end)
{
if (start >= end)
{
return true;
}
int a = preorder[start];
int i = 0;
for (i = start + 1; i <= end; i++)
{
if (preorder[i] >= a)
{
break;
}
}
for (int j = i; j <= end; j++)
{
if (preorder[j] < a)
{
return false;
}
}
return checkBST(start + 1, i - 1) && checkBST(i, end);
}
bool checkMirrorBST(int start, int end)
{
if (start >= end)
{
return true;
}
int a = preorder[start];
int i = 0;
for (i = start + 1; i <= end; i++)
{
if (preorder[i] < a)
{
break;
}
}
for (int j = i; j <= end; j++)
{
if (preorder[j] >= a)
{
return false;
}
}
return checkMirrorBST(start + 1, i - 1) && checkMirrorBST(i, end);
}
void postPrintBST(int start, int end, int kind)
{
if (start > end)
{
return;
}
int a = preorder[start];
int i = 0;
if (kind == 1)
{
for (i = start + 1; i <= end; i++)
{
if (preorder[i] >= a)
{
break;
}
}
}
else if (kind == -1)
{
for (i = start + 1; i <= end; i++)
{
if (preorder[i] < a)
{
break;
}
}
}
postPrintBST(start + 1, i - 1, kind);
postPrintBST(i, end, kind);
postorder.push_back(a);
}
int main()
{
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
scanf("%d", &preorder[i]);
}
if (checkBST(0, N - 1))
{
postPrintBST(0, N - 1, 1);
printf("YES\n");
for (int i = 0; i < postorder.size(); i++)
{
if (i == 0)
{
printf("%d", postorder[i]);
continue;
}
printf(" %d", postorder[i]);
}
}
else if (checkMirrorBST(0, N - 1))
{
postPrintBST(0, N - 1, -1);
printf("YES\n");
for (int i = 0; i < postorder.size(); i++)
{
if (i == 0)
{
printf("%d", postorder[i]);
continue;
}
printf(" %d", postorder[i]);
}
}
else
{
printf("NO\n");
}
return 0;
} 总之，看到二叉树就遍历。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int maxn = 1009;
int input[maxn];
vector<int>output[2];
//judge if every left son is smaller than itself and
//every right son is bigger than or equal to itself
bool judge1(int l, int r){
if (r < l) return true;
int root = input[l]; //the first node is the root of tree
//next we should find the boundary of left subtree and right subtree
int mid = l+1;
while (input[mid] < root && mid<=r) mid++;//input[mid] is the right son of it node
//according to the rule, all node in right tree much not smaller than root
for (int j = mid; j <= r; j++){
if (input[j] < root) return false;
}
//check two subtree with the same rule
if (!judge1(l+1, mid-1)) return false;
if (!judge1(mid, r)) return false;
//recorde the ans
output[0].push_back(root);
return true;
}
//judst like judge1(), but now right all subtree node should smaller thean itself
bool judge2(int l, int r){
if (r < l) return true;
int root = input[l];
int mid = l + 1;
while (input[mid] >= root && mid<=r) mid++;
for (int j = mid; j < r; j++){
if (input[j] >= root) return false;
}
if (!judge2(l + 1, mid - 1)) return false;
if (!judge2(mid, r)) return false;
output[1].push_back(root);
return true;
}
//output the ans according to the require of problem
void display(vector<int>t){
cout << "YES" << endl;
cout << t[0];
for (int i = 1; i < t.size(); i++) cout << " " << t[i];
cout << endl;
}
int main(){
//get input data
int n;
cin >> n;
for (int i = 0; i < n; i++){
scanf("%d", &input[i]);
}
//judge if the data is accord to the value
if (input[0]>input[1]){
if (!judge1(0, n - 1)) cout << "NO" << endl;
else display(output[0]);
}
else{
if (!judge2(0, n - 1)) cout << "NO" << endl;
else display(output[1]);
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1010;
int n,key,index=0;
vector<int> data,pre,prem,Post,Postm;
struct node{
int data;
int lchild,rchild;
}Node[maxn];
void insert(int &root,int x){
if(root==-1){
Node[index].data=x;
Node[index].lchild=-1;
Node[index].rchild=-1;
root=index++;
return;
}
if(x>=Node[root].data)
insert(Node[root].rchild,x);
else insert(Node[root].lchild,x);
}
void Preorder(int root){
if(root==-1) return;
pre.push_back(Node[root].data);
Preorder(Node[root].lchild);
Preorder(Node[root].rchild);
Post.push_back(Node[root].data);
}
void mirrorPreorder(int root){
if(root==-1) return;
prem.push_back(Node[root].data);
mirrorPreorder(Node[root].rchild);
mirrorPreorder(Node[root].lchild);
Postm.push_back(Node[root].data);
}
int main(){
cin>>n;
int root=-1;
for(int i=0;i<n;i++){
cin>>key;
data.push_back(key);
insert(root,key);
}
Preorder(0);
mirrorPreorder(0);
if(pre==data){
cout<<"YES"<<endl;
for(int i=0;i<Post.size();i++){
cout<<Post[i];
if(i!=Post.size()-1) cout<<" ";
}
}
else if(prem==data){
cout<<"YES"<<endl;
for(int i=0;i<Postm.size();i++){
cout<<Postm[i];
if(i!=Postm.size()-1) cout<<" ";
}
}
else cout<<"NO";
return 0;
}
1043 Is It a Binary Search Tree
题目给出二叉树的前序序列判断是否是BST 是输出YES 并且输出改BST的后序序列
通过前序和中序 来 求后序。
由于是BST 所有数据的中序一定是有序的。题目说给的前序序列可能是 左右交换过的BST 所以需要先判断一下，如果是镜像的 BST 那么他的前序的第二个一定是大于根节点也就是第一个。
if(CNT>1){
if(Pre[1]>=Pre[0]) {
ismirr =true;
sort(In.begin(),In.end(),greater<int>());
}
else{
ismirr =false;
sort(In.begin(),In.end(),less<int>());
}
} 而对应的中序序列 也需要 减序 排列。
此上 得到中序序列。
由前序和中序求 后序
[ Pre] 8 6 5 7 10 8 11
[ In ] 5 6 7 8 8 10 11
[Post] ? ? ? ? ? ? ?
↓↓↓↓ //在In 里面查找根节点 pre[0]; 如果是非镜像的BST 则从前往后寻找，如果是镜像则从 //后往前
[ Pre] 8 6 5 7 10 8 11
[↑]-----//前序从根节点开始往后len =3 个结点是 8的左子树的前序序列
[ In ] 5 6 7 8 8 10 11
------[↑] //中序左边是bst 左边的 长度为3 的序列时 左子树的中序序列
[Post] ? ? ? ? ? ? 8
[↑] [↑] //后序的根节点的位置以及右子数的根节点
左 右 由上可知，反之得到右子数的前序和中序 。
这样就可以用递归的思想来计算 二叉树，每一次递归可以归位一个后序的根节点。
如果不是BST 的情况呢？
如果在对应的区域找不到当前的根节点 则可以说明不是BST前序序列。（具体原因 可以用题目给出的 样例3 推导一下。
AC代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Node{
int p_low,p_high, i_low, i_high, post_pos;
int len_l;
int len_r;
bool find =false;
};
Node S[1001]; //在这里我使用了自己模拟一个栈。在AC之前RE了
int top =-1; //很久,当然你也可以把这些变量放在函数的参数里面
vector <int> Pre,In,Post;
int root,i;
int CNT;
bool ismirr =false;
bool isBST(){
root =Pre[S[top].p_low];
if(ismirr){
for(i=S[top].i_high;i>=S[top].i_low;i--){
if(In[i]==root){
S[top].find =true;
break;
}
}
}
else {
for(i=S[top].i_low;i<=S[top].i_high;i++){
if(In[i]==root){
S[top]. find =true;
break;
}
}
}
if(S[top].find){
Post[S[top].post_pos] =In[i];
S[top].len_l = i-S[top].i_low;
S[top].len_r =S[top].i_high-i;
bool ret_l =true,ret_r=true;
if(S[top].len_l!=0){
Node t;
t.p_low =S[top].p_low+1;
t.p_high =S[top].p_low+S[top].len_l;
t.i_low =S[top].i_low;
t.i_high =S[top].i_low+S[top].len_l-1;
t.post_pos =S[top].post_pos-S[top].len_r-1;
S[++top] =t;
ret_l=isBST();
}
if(S[top].len_r!=0){
Node t;
t.p_low =S[top].p_high-S[top].len_r+1;
t.p_high =S[top].p_high;
t.i_low =S[top].i_high-S[top].len_r+1;
t.i_high =S[top].i_high;
t.post_pos =S[top].post_pos-1;
S[++top] =t;
ret_r =isBST();
}
--top;
return ret_l&&ret_r;
}
else{
--top;
return false;
}
}
int main(){
cin>>CNT;
Pre.resize(CNT);
In.resize(CNT);
Post.resize(CNT);
for(int i=0;i<CNT;i++){
cin>>Pre[i];
In[i]=Pre[i];
}
if(CNT>1){
if(Pre[1]>=Pre[0]) {
ismirr =true;
sort(In.begin(),In.end(),greater<int>());
}
else{
ismirr =false;
sort(In.begin(),In.end(),less<int>());
}
}
S[++top] =Node{0,Pre.size()-1,0,In.size()-1,Post.size()-1};
if(isBST()){
cout<<"YES"<<endl;
cout<<Post[0];
for(int i =1;i<Post.size();i++){
cout<<" "<<Post[i];
}
}
else{
cout<<"NO"<<endl;
}
return 0;
}#include<string>
#include<cstdio>
#include<vector>
using namespace std;
struct Node
{
Node *left;
Node *right;
int data;
};
int input[1010];
int total = 0;
bool output_bool = true;
vector<int> output_houxu;
void xianxu(Node *tmp)
{
//cout<<tmp->data<<endl;
if(tmp->data!=input[total++]) output_bool = false;
if(tmp->left!=NULL)
xianxu(tmp->left);
if(tmp->right !=NULL)
xianxu(tmp->right);
}
void houxu(Node *tmp)
{
if(tmp->left!=NULL)
houxu(tmp->left);
if(tmp->right !=NULL)
houxu(tmp->right);
output_houxu.push_back(tmp->data);
}
int main()
{
bool isReverse = false;
int N;
scanf("%d",&N);
if(N==1)
{
int tmp;
scanf("%d",&tmp);
cout<<"YES"<<endl;
cout<<tmp<<endl;
return 0;
}
Node *root=new Node;
for(int i=0;i<N;i++)
{
scanf("%d",&input[i]);
if(i==0)
{
//root
root->data=input[0];
root->left = NULL;
root->right=NULL;
continue;
}
if(i==1&&input[0]<input[1])
{
isReverse = true;
}
Node *now = new Node;
now->data = input[i];
now->left = NULL;
now->right = NULL;
if(!isReverse)
{
//正常顺序
Node *tmp = root;
while(1)
{
if(input[i]<tmp->data)
{
if(tmp->left!=NULL)
{
tmp=tmp->left;
continue;
}else
{
tmp->left = now;
break;
}
}else
{
if(tmp->right!=NULL)
{
tmp=tmp->right;
continue;
}else
{
tmp->right = now;
break;
}
}
}
}else
{
//镜像顺序
Node *tmp = root;
while(1)
{
if(input[i]<tmp->data)
{
if(tmp->right!=NULL)
{
tmp=tmp->right;
continue;
}else
{
tmp->right = now;
break;
}
}else
{
if(tmp->left!=NULL)
{
tmp=tmp->left;
continue;
}else
{
tmp->left = now;
break;
}
}
}
}
}
xianxu(root);
if(output_bool)
{
cout<<"YES"<<endl;
houxu(root);
for(int i=0;i<output_houxu.size();i++)
{
cout<<output_houxu[i];
if(i!=output_houxu.size()-1)
cout<<" ";
}
cout<<endl;
}else
{
cout<<"NO"<<endl;
}
return 0;
}
题目要求输入二叉搜索数的前序或者是镜像前序。这两种搜索方式都是属于前序搜索，因此可以获得一个前序的很重要的信息，即树前序序列的第一个序号为根结点。
二叉搜索树有一个性质是，其中序序列是非递减排序序列。
因此我们假设输入的树是一颗二叉搜索书，将所有结点都进行排序，得到二叉搜索树的中序序列。
由树的前序和中序确定一颗唯一二叉树的性质，可以检验该树是否存在。假如存在则表示存在答案。
前序和中序之所以可以确定一个唯一二叉树，是因为前序确定了根节点，中序确定了根结点的左部分和右部分。然后根据二叉树的递归定义逐渐构造一颗唯一二叉树。
A
/ \
B C
/ \ / \
... ...
前序：| A | B.... | C.... |
^ ^ ^ ^ ^
a s1 e1 s2 e2
A肯定为根结点。(B....)的大小只根据前序是无法确定的。令其为sizeof(B....)。
s1 = a + 1; ①
e1 = a + sizeof(..B..); ②
s2 = a + sizeof(..B..) + 1; ③
e2 = end;//区域最后一个位置
中序：| ..B.. | A | ..C.. |
^ ^ ^ ^ ^
s1 e1 m s2 e2
m是在中序序列中寻找第一个等于A的位置。（是第一个，而不是与A一样的其他位置的值，是由二叉搜索树的定义确定的）
根据中序可以确定(..B..)的大小，令其为sizeof(..B..)表示。
sizeof(..B..) = m - s1; ④
显然sizeof(B....)=sizeof(..B..)。因为先序搜索只有遍历完A的左半部才会去访问C，及C之后的结点。
将公式④带入带入①②③得：
s1 = a + 1; ①
e1 = a + m - s1; ②
s2 = a + m - s1 + 1; ③
e2 = end;//区域最后一个位置
那么就可以开始递归调用了。
小结：关键在于确定e1和s2变量，其是由中序根结点左部分大小计算而来的。
那假如前序变为镜像前序呢？自然就需要使用中序根结点右部分去计算。
镜像前序：|A|C....|B....|
中序：|..B..|A|..C..|
使用sizeof(..C..)的大小去计算镜像前序的(..C..)的区域。
#include
using namespace std;
int a[1001], b[1001], n, k = 0, isMirror = 0;
bool flag[2] = {true,true};
bool cmp(int a,int b){
if(isMirror == 0){
return a < b;
}else{
return a >= b;
}
}
void isBST(int i,int len){
if(!flag[isMirror]) return;
if(len == 0){
}else if(len == 1){
b[k++] = a[i];
}else{
int x,y;
for(x = i+1; cmp(a[x],a[i]) && x<i+len; x++);
isBST(i+1,x-i-1);
for(y = x; !cmp(a[y],a[i]) && y<i+len; y++);
if(y != i+len) flag[isMirror] = false;
isBST(x,y-x);
b[k++] = a[i];
}
}
int main(){
//freopen("in/in.txt","r",stdin);
cin >> n;
for(int i = 0; i > a[i];
isBST(0,n);
if(!flag[isMirror]){
k = 0;
isMirror = 1;
isBST(0,n);
}
if(flag[0] || flag[1]){
printf("YES\n");
for(int i = 0; i < n-1; i++){
printf("%d ",b[i]);
}
printf("%d",b[n-1]);
}else{
printf("NO");
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
vector<int> origin,pre,preM,post,postM;
struct node {
int data;
node *lchild,*rchild;
node() {}
node(int a):data(a),lchild(NULL),rchild(NULL) {
}
};
void Insert(node* & root,int x) {
if(root==NULL) {
root=new node(x);
return ;
}
if(x<root->data) {
Insert(root->lchild,x);
} else {
Insert(root->rchild,x);
}
}
void preorder(node* root,vector<int> & v) {
if(root==NULL) {
return ;
}
v.emplace_back(root->data);
preorder(root->lchild,v);
preorder(root->rchild,v);
}
void preorderM(node* root,vector<int> & v) {
if(root==NULL) {
return ;
}
v.emplace_back(root->data);
preorderM(root->rchild,v);
preorderM(root->lchild,v);
}
void postorder(node* root,vector<int> & v) {
if(root==NULL) {
return ;
}
postorder(root->lchild,v);
postorder(root->rchild,v);
v.emplace_back(root->data);
}
void postorderM(node* root,vector<int> & v) {
if(root==NULL) {
return ;
}
postorderM(root->rchild,v);
postorderM(root->lchild,v);
v.emplace_back(root->data);
}
int main() {
int n;
while(cin>>n) {
node* root=NULL;
for(int i=0; i<n; i++) {
int temp;
cin>>temp;
origin.emplace_back(temp);
Insert(root,temp);
}
preorder(root,pre);
preorderM(root,preM);
postorder(root,post);
postorderM(root,postM);
if(origin==pre) {
cout<<"YES"<<endl;
for(int i=0;i<post.size();i++){
cout<<post[i];
if(i<post.size()-1){
cout<<" ";
}
else{
cout<<endl;
}
}
}
else if(origin==preM) {
cout<<"YES"<<endl;
for(int i=0;i<postM.size();i++){
cout<<postM[i];
if(i<postM.size()-1){
cout<<" ";
}
else{
cout<<endl;
}
}
}
else{
cout<<"NO"<<endl;
}
}
return 0;
} 
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 1005;
struct Node {
int val;
Node* l;
Node* r;
Node(int val, Node* l, Node* r) {
this->val = val;
this->l = l;
this->r = r;
}
};
int n;
bool image = false;
Node* none = new Node(-0x3f3f3f3f, nullptr, nullptr);
Node* build(vector<int>& pre, vector<int>& mid) {
int sz = pre.size();
if (sz == 0) return nullptr;
// 由前序拿到根
int root = pre[0];
Node* r = none;
int p = -1;
// 在中序中找到左子树和右子树
if (!image) {
for (int i = 0; i < mid.size(); i++) {
if (mid[i] == root) {
p = i;
break;
}
}
} else {
for (int i = mid.size() - 1; i >= 0; i--) {
if (mid[i] == root) {
p = i;
break;
}
}
}
if (p == -1) return none;
vector<int> l_pre, l_mid, r_pre, r_mid;
Node* node = new Node(root, nullptr, nullptr);
for (int j = 1; j <= p; j++) l_pre.push_back(pre[j]);
for (int j = 0; j < p; j++) l_mid.push_back(mid[j]);
for (int j = p + 1; j < sz; j++) {
r_pre.push_back(pre[j]);
r_mid.push_back(mid[j]);
}
node->l = build(l_pre, l_mid);
node->r = build(r_pre, r_mid);
if (node->l != none && node->r != none) {
r = node;
} else
delete node;
return r;
}
void post_order(Node* cur) {
if (cur == nullptr) return;
post_order(cur->l);
post_order(cur->r);
cout << cur->val << ' ';
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> n;
vector<int> pre(n), mid(n);
for (int i = 0; i < n; i++) {
cin >> pre[i];
mid[i] = pre[i];
}
sort(mid.begin(), mid.end());
if (n == 1) {
if (pre[0] == mid[0]) {
puts("YES");
cout << pre[0];
} else {
puts("NO");
}
return 0;
}
if (pre[1] > pre[0]) {
image = true;
reverse(mid.begin(), mid.end());
}
Node* t = build(pre, mid);
if (t != none) {
puts("YES");
post_order(t);
} else
puts("NO");
return 0;
} 
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node* left;
Node* right;
};
void insert(Node* &root,int data){
if(root==NULL){
root=new Node;
root->data=data;
root->left=NULL;
root->right=NULL;
}else{
if(data<root->data){
insert(root->left,data);
}else if(data>root->data){
insert(root->right,data);
}else if(data==root->data){
insert(root->right,data);
}
}
}
void createTree(Node* &root,vector<int> num,int n){
root=NULL;
for(int i=0;i<n;i++)insert(root,num[i]);
}
void PreOrder(Node* root,vector<int> &vi){
if(root!=NULL){
vi.push_back(root->data);
PreOrder(root->left,vi);
PreOrder(root->right,vi);
}
}
void PreOrderMirr(Node* root,vector<int> &vi){
if(root!=NULL){
vi.push_back(root->data);
PreOrderMirr(root->right,vi);
PreOrderMirr(root->left,vi);
}
}
bool isSame(vector<int> v1,vector<int> v2){
int len1=v1.size();
int len2=v2.size();
if(len1!=len2){
return false;
}else{
for(int i=0;i<len1;i++){
if(v1[i]!=v2[i])return false;
}
}
return true;
}
int sum=0;
void PostOrder(Node* root,int n){
if(root!=NULL){
PostOrder(root->left,n);
PostOrder(root->right,n);
if(sum<n-1){
printf("%d ",root->data);
sum++;
}else{
printf("%d\n",root->data);
}
}
}
void PostOrderMirr(Node* root,int n){
if(root!=NULL){
PostOrderMirr(root->right,n);
PostOrderMirr(root->left,n);
if(sum<n-1){
printf("%d ",root->data);
sum++;
}else{
printf("%d\n",root->data);
}
}
}
int main(){
int n;
while(~scanf("%d",&n)){
vector<int> num;
Node* root;
for(int i=0;i<n;i++){
int temp;
scanf("%d",&temp);
num.push_back(temp);
}
//cout<<"1"<<endl;
createTree(root,num,n);
vector<int> v1,v2;
PreOrder(root,v1);
PreOrderMirr(root,v2);
if(isSame(v1,num)||isSame(v2,num)){
printf("YES\n");
if(isSame(v1,num)){
PostOrder(root,v1.size());
}else if(isSame(v2,num)){
PostOrderMirr(root,v2.size());
}
}else{
printf("NO\n");
}
}
return 0;
} 
//BST 这里可根据前序遍历加上二叉树特性（左<根<右（递归））来建立，也可根据前序和中序遍历来建立
//显然这里采用第一种方式简便一点,如果建立的树的线序遍历和给出的序列不符则说明No
//对于第二种方式，当建树不成功（找不到根节点）的时候则说明No
//镜像BST 直接在建树的时候与原来的树反之即可，根据第二个输入和第一个输入的大小就可以知道是否是镜像BST。
#include<iostream>
(720)#include<vector>
using namespace std;
struct BST {
int val;
BST* left;
BST* right;
BST(int a) :val(a), left(NULL), right(NULL) {}
};
void Insert(BST* &root, int val) {//要么返回root，要么形参用 “引用”
if (!root) {
root = new BST(val);
root->left = NULL;
root->right = NULL;
}
else if (root->val > val) {
Insert(root->left, val);
}
else {
Insert(root->right, val);
}
}
void MirrorInsert(BST* &root, int val) {
if (!root) {
root = new BST(val);
root->left = NULL;
root->right = NULL;
}
else if (root->val > val) {
MirrorInsert(root->right, val);
}
else {
MirrorInsert(root->left, val);
}
}
void preOrder(vector<int> &result, BST* root) {
if (root) {
result.push_back(root->val);
preOrder(result, root->left);
preOrder(result, root->right);
}
}
void postOrder(vector<int> &result, BST* root) {
if (root) {
postOrder(result, root->left);
postOrder(result, root->right);
result.push_back(root->val);
}
}
int main() {
int n, x;
cin >> n;
BST* root = NULL;
vector<int>sequence;
for (int i = 0; i < n; i++) {
cin >> x;
sequence.push_back(x);
if (i >= 1 && sequence[1] >= sequence[0]) {//说明是镜像BST
MirrorInsert(root,x);
}
else{
Insert(root, x);
}
}
vector<int>result;
preOrder(result, root);
if (result == sequence) {
printf("YES\n");
result.clear();
postOrder(result, root);
for (int i = 0; i < result.size(); i++) {
if (i) { printf(" "); }
printf("%d", result[i]);
}
}
else {
printf("NO");
}
} 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static class Node {
int val;
Node left;
Node right;
public Node() {
}
public Node(int data) {
this.val = data;
this.left = null;
this.right = null;
}
public Node Insert(Node node, int data) {
if (node == null) {
node = new Node(data);
} else {
if (data < node.val) node.left = Insert(node.left, data);
else node.right = Insert(node.right, data);
}
return node;
}
}
public static void main(String[] args) {
List<Integer> tree = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
List<Integer> tempmirror = new ArrayList<>();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node s = new Node(sc.nextInt());
tree.add(s.val);
for (int i = 1; i < n; i++) {
int data = sc.nextInt();
tree.add(data);
s.Insert(s, data);
}
PreOrder(s, temp);
PreMirrorOrder(s,tempmirror);
if (tree.equals(temp)){
System.out.println("YES");
temp.clear();
PostOrder(s,temp);
for (int i=0;i<temp.size()-1;i++){
System.out.print(temp.get(i)+" ");
}
System.out.println(temp.get(temp.size()-1));
}else if(tree .equals(tempmirror)){
System.out.println("YES");
temp.clear();
PostMirrorOrder(s,temp);
for (int i=0;i<temp.size()-1;i++){
System.out.print(temp.get(i)+" ");
}
System.out.println(temp.get(temp.size()-1));
}else {
System.out.println("NO");
}
}
private static void PreOrder(Node node, List<Integer> list) {
if (node == null) return;
list.add(node.val);
PreOrder(node.left, list);
PreOrder(node.right, list);
}
private static void PreMirrorOrder(Node node, List<Integer> list) {
if (node == null) return;
list.add(node.val);
PreMirrorOrder(node.right, list);
PreMirrorOrder(node.left, list);
}
private static void PostOrder(Node node, List<Integer> list) {
if (node == null) return;
PostOrder(node.left, list);
PostOrder(node.right, list);
list.add(node.val);
}
private static void PostMirrorOrder(Node node, List<Integer> list) {
if (node == null) return;
PostMirrorOrder(node.right, list);
PostMirrorOrder(node.left, list);
list.add(node.val);
}
}
不需要交换，只需要镜像遍历就可以了，我真是傻还一直交换左右子树然后在遍历，而且pat官网第四个一直过不去，
#include<iostream>
#include<stdlib.h>
#include<vector>
using namespace std;
typedef struct BSTNode {
int data;
struct BSTNode *lchild, *rchild;
}BSTNode,*BSTree;
void create(BSTree &root, int data);
void create(BSTree &root, int data);
void preTravel(BSTree root);
void postTravel(BSTree root);
void mirPostTravel(BSTree root);
void mirPreTravel(BSTree root);
int n = 0,number = 0;
BSTree t;
vector<int> mirPre,mirPost, pre,post,num,temNode;
bool flag = false;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> number;
num.push_back(number);
create(t, number);
}
preTravel(t);
postTravel(t);
mirPreTravel(t);
mirPostTravel(t);
if ((flag = (num==pre)) || num==mirPre) {
cout << "YES" << endl;
temNode = flag ? post : mirPost;
cout << temNode[0];
for (auto i = temNode.begin()+1; i != temNode.end(); i++) {
cout <<" "<< *i;
}
cout << endl;
}
else {
cout << "NO" << endl;
}
system("pause");
return 0;
}
void preTravel(BSTree root) {//原二叉树先序遍历
if (root == NULL)return;
pre.push_back(root->data);
if (root->lchild != NULL)preTravel(root->lchild);
if (root->rchild != NULL)preTravel(root->rchild);
}
void mirPreTravel(BSTree root) {//原二叉树先序遍历
if (root == NULL)return;
mirPre.push_back(root->data);
if (root->rchild != NULL)mirPreTravel(root->rchild);
if (root->lchild != NULL)mirPreTravel(root->lchild);
}
void postTravel(BSTree root) {//二叉树后序遍历
if (root == NULL)return;
if (root->lchild != NULL)postTravel(root->lchild);
if (root->rchild != NULL)postTravel(root->rchild);
post.push_back(root->data);
}
void mirPostTravel(BSTree root) {//二叉树后序遍历
if (root == NULL)return;
if (root->rchild != NULL)mirPostTravel(root->rchild);
if (root->lchild != NULL)mirPostTravel(root->lchild);
mirPost.push_back(root->data);
}
void create(BSTree &root, int data) {//还原二叉树
if (root == NULL) {
root = (BSTree)malloc(sizeof(BSTNode));
root->data = data;
root->lchild = NULL;
root->rchild = NULL;
return;
}
if (data < root->data)create(root->lchild, data);
else create(root->rchild, data);
}
class Node:
def __init__(self,value=-1):
self.value = value
self.left = None
self.right = None
class Tree:
def __init__(self):
self.root = None
def isEmpty(self):
if self.root.value==-1:
return True
else:
return False
def add(self,val):
node = Node(val)
if self.root is None:
self.root = node
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
if cur_node.value>val:
if cur_node.left is None:
cur_node.left = node
return
else:
queue.append(cur_node.left)
else:
if cur_node.right is None:
cur_node.right = node
return
else:
queue.append(cur_node.right)
def addmirror(self,val):
node = Node(val)
if self.root is None:
self.root = node
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
if cur_node.value<=val:
if cur_node.left is None:
cur_node.left = node
return
else:
queue.append(cur_node.left)
else:
if cur_node.right is None:
cur_node.right = node
return
else:
queue.append(cur_node.right)
def preorder(self,out):
if self.isEmpty():
return
stack = []
now_node = self.root
while now_node or stack:
while now_node:
out.append(now_node.value)
stack.append(now_node)
now_node = now_node.left
if stack:
now_node = stack.pop()
now_node = now_node.right
def postorder(self,out):
if self.isEmpty():
return
node = self.root
stack1,stack2 = [],[]
stack1.append(node)
while stack1:
node = stack1.pop()
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
stack2.append(node)
while stack2:
out.append(stack2.pop().value)
n = input()
num = list(map(int,input().split()))
root,mroot = Tree(),Tree()
for i in num:
root.add(i)
mroot.addmirror(i)
pre,mpre = [],[]
root.preorder(pre)
mroot.preorder(mpre)
post,mpost = [],[]
root.postorder(post)
mroot.postorder(mpost)
if num==pre:
print("YES")
print(' '.join(map(str,post)))
elif num==mpre:
print("YES")
print(' '.join(map(str,mpost)))
else:
print('NO')
这道题难度很大，也许是我没有找到巧妙的方法吧，我是先构建了二叉树和它的镜像，然后在分别取出它们前序遍历和后序遍历的结果，最后进行比较并输出。
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
