Powered by:NEFU AB-IN
Link
文章目录
- A1064 Complete Binary Search Tree
- 题意
- 思路
- 代码
A1064 Complete Binary Search Tree
-
题意
二叉搜索树 (BST) 递归定义为具有以下属性的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
它的左、右子树也分别为二叉搜索树
完全二叉树 (CBT) 定义为除最深层外的其他层的结点数都达到最大个数，最深层的所有结点都连续集中在最左边的二叉树。
现在，给定 N 个不同非负整数，表示 N 个结点的权值，用这 N 个结点可以构成唯一的完全二叉搜索树。
请你输出该完全二叉搜索树的层序遍历。 -
思路
完全二叉树可以用一维数组存，按中序遍历的顺序填进去即可
-
代码
/* * @Author: NEFU AB-IN * @Date: 2022-09-12 20:20:02 * @FilePath: \GPLT\A1064\A1064.cpp * @LastEditTime: 2022-09-12 20:24:56 */ #include <bits/stdc++.h> using namespace std; #define N n + 100 #define int long long #define SZ(X) ((int)(X).size()) #define IOS \ios::sync_with_stdio(false); \cin.tie(nullptr); \cout.tie(nullptr) #define DEBUG(X) cout << #X << ": " << X << '\n' typedef pair<int, int> PII;// #undef N // const int N = 1e5 + 10;// #undef intsigned main() {IOS;int n;cin >> n;vector<int> w(n), tr(N);for (int i = 0; i < n; ++i)cin >> w[i];sort(w.begin(), w.end());int id = 0;function<void(int)> dfs = [&](int u) {if (u * 2 <= n)dfs(u * 2);tr[u] = w[id++];if (u * 2 + 1 <= n)dfs(u * 2 + 1);};dfs(1);cout << tr[1];for (int i = 2; i <= n; ++i){cout << " " << tr[i];}return 0; }
