思路:
1.主要分为两个部分:
2.构建二叉搜索树。
3.判断是否是完全二叉树。
构建二叉搜索树:
1.判断当前结点是否为空,如果为空,创建新结点,并将新结点的权值赋值为传入的参数。
2.如果当前结点不为空,那么判断新传入的参数与当前结点权值的大小,根据要求选择左右递归。
3.这里我们是左大右小的BST:
4.比如如果插入的新值大于当前值,那么insert(l[u],x),继续向左递归。
5.反之,向右递归。
6.这样一棵BST就建好了。
BST建树代码:
void insert(int &u, int x)
{
if (!u)
{
u = ++idx;
w[u] = x;
}
else if (x > w[u])
{
insert(l[u], x);
}
else if (x < w[u])
{
insert(r[u], x);
}
}
判断是否是完全二叉树:
1.完全二叉树就是所有结点向左边靠拢(这里不多阐述完全二叉树的定义)。
2.我们可以直接层序遍历,第一次遇到空节点做标记。
3.如果出现两次空节点,那么就可以判定不是完全二叉树了(这里不是特别具体)。
4.我尝试给个图...
简单讲解:
1.黑点就是真正插入的点,红点是其衍生出的空点。
2.空点不会衍生出空点,但黑点衍生出的空点也要入队。
3.当空点出队时进行判断,如果是第一次遇见就要打上标记。(空节点不需要子节点入队判断)
4.接下来如果能遇到非空点,说明在同一层存在空节点在非空节点的左边,或者
5.存在空节点在深层非空节点的上层,这都可以判断出他不是完全二叉树。
6.也就是说,如果第一次遇到空节点打上标记了,接下来只要还有非空结点,就不是完全二叉树。
判断是否是完全二叉树:
void bfs()
{
queue<int> q;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
if (t == 0)
{
if (!flag)
{
flag = true;
}
continue;
}
else
{
if (flag)
{
iswan = false;
}
}
ans.push_back(w[t]);
if (l[t])
{
q.push(l[t]);
}
else
{
q.push(0);
}
if (r[t])
{
q.push(r[t]);
}
else
{
q.push(0);
}
}
}
#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 root;
int idx;
vector<int> ans;
bool flag = false;
bool iswan = true;
void insert(int &u, int x)
{
if (!u)
{
u = ++idx;
w[u] = x;
}
else if (x > w[u])
{
insert(l[u], x);
}
else if (x < w[u])
{
insert(r[u], x);
}
}
void bfs()
{
queue<int> q;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
if (t == 0)
{
if (!flag)
{
flag = true;
}
continue;
}
else
{
if (flag)
{
iswan = false;
}
}
ans.push_back(w[t]);
if (l[t])
{
q.push(l[t]);
}
else
{
q.push(0);
}
if (r[t])
{
q.push(r[t]);
}
else
{
q.push(0);
}
}
}
void solve()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
insert(root, x);
}
bfs();
for (int i = 0; i < n; i++)
{
printf("%d", ans[i]);
if (i != n - 1)
{
printf(" ");
}
else
{
puts("");
}
}
if (iswan)
{
puts("YES");
}
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
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/