题意:
1.题目中的BST是左键严格小于,右键大于等于。
2.题目给你一个二叉树的先序遍历序列。
3.如果这个序列是某个符合上述要求的二叉树的先序遍历或者是镜像二叉树的先序遍历就判断ok
4.同时输出原本二叉树的后序遍历(就是镜像二叉树要复原然后求后序遍历)。
思路:
1.根据先序遍历序列构建BST。
2.对树分别做一次先序遍历和镜像先序遍历。
3.然后将题目给的序列和我们得到的两个序列比较。
4.和哪个一模一样就按要求进行后序遍历。
镜像遍历:
1.其实就是搜索顺序反过来。
2.比如我们正常遍历都是先向左儿子递归,再向右儿子递归。
3.如果镜像的我们先向右儿子递归,再向左儿子递归就好了。
4.先序遍历和后序遍历保持原本操作即可。
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
typedef long long LL;
const int N = 1e5 + 10;
// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;
// const int P = 1 << 10;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<LL, int> PLI;
typedef pair<int, string> PIS;
typedef pair<double, int> PDI;
typedef pair<string, int> PSI;
const double eps = 1e-4;
const int mod = 1e9 + 7;
int n, k;
int m;
int Q;
// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
int w[N];
int l[N];
int r[N];
int idx;
int root;
vector<int> pre, mirpre, ans;
void insert(int &u, int x)
{
if (!u)
{
u = ++idx;
w[u] = x;
return;
}
if (x < w[u])
{
insert(l[u], x);
}
else if (x >= w[u])
{
insert(r[u], x);
}
}
void preo(int u)
{
pre.push_back(w[u]);
if (l[u])
{
preo(l[u]);
}
if (r[u])
{
preo(r[u]);
}
}
// 镜面先序遍历,就是先搜右后搜左
void mirpreo(int u)
{
mirpre.push_back(w[u]);
if (r[u])
{
mirpreo(r[u]);
}
if (l[u])
{
mirpreo(l[u]);
}
}
void posto(int u)
{
if (l[u])
{
posto(l[u]);
}
if (r[u])
{
posto(r[u]);
}
ans.push_back(w[u]);
}
void mirposto(int u)
{
if (r[u])
{
mirposto(r[u]);
}
if (l[u])
{
mirposto(l[u]);
}
ans.push_back(w[u]);
}
void solve()
{
scanf("%d", &n);
vector<int> v(n);
for (int i = 0; i < n; i++)
{
scanf("%d", &v[i]);
insert(root, v[i]);
}
preo(root);
mirpreo(root);
int type = 0;
// for (auto c : pre)
// {
// cout << c << ' ';
// }
// cout<<endl;
if (v == pre)
{
// cout << 1 << endl;
type = 1;
}
if (v == mirpre)
{
// cout << 1 << endl;
type = 2;
}
if (type == 1)
{
puts("YES");
posto(root);
for (int i = 0; i < n; i++)
{
printf("%d", ans[i]);
if (i != n - 1)
{
printf(" ");
}
}
}
else if (type == 2)
{
mirposto(root);
puts("YES");
for (int i = 0; i < n; i++)
{
printf("%d", ans[i]);
if (i != n - 1)
{
printf(" ");
}
}
}
else
{
puts("NO");
}
}
int main()
{
int t = 1;
// init(1000000);
// scanf("%d", &t);
// int a = 1;
// for (int i = 1; i <= 26; i++)
// {
// a = (a << 1) + 1;
// }
// cout << a << endl;
// float t = 134217727;
// int cnt = 200;
// printf("%.16lf", t);
// while (cnt--)
// {
// t = t * 2 + a;
// printf("%.16f\n", t);
// }
// getchar();
while (t--)
{
// cout << (2563 % 11) << endl;
// cout << t << endl;
solve();
// cout << (((float)1) << 63) << endl;
// cout << '\0' << endl;
// cout << f(4);
// cout<<(25 >> 5)
// cout << gcd(31415, 14142);//
// cout << (28284 / 11) << endl;
}
return 0;
}
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. _|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~_ _-~ /\
* / \ __ \/~ __
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* 神兽保佑 永无BUG
*/
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/