当前位置:网站首页>1064 Complete Binary Search Tree
1064 Complete Binary Search Tree
2022-07-30 21:37:00 【Brosto_Cloud】
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
- Both the left and right subtrees must also be binary search trees.
A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
p>Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line areseparated by a space and are no greater than 2000.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of theline.
Sample Input:
101 2 3 4 5 6 7 8 9 0
Sample Output:
6 3 8 1 5 7 9 0 2 4
For BST, the in-order traversal is a non-decreasing sequence, so first sort from small to large, build the tree according to the in-order traversal, and then output according to the serial number (ie, level order traversal):
#include #include using namespace std;int a[1010], n, ans[1010], cnt;void dfs(int x) {if (x <= n) {dfs(x * 2);ans[x] = a[cnt++];dfs(x * 2 + 1);}}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}sort(a, a + n);dfs(1);for (int i = 1; i <= n; i++) {cout << ans[i];if (i != n) {cout << ' ';}}return 0;}
边栏推荐
- (7/29) Basic board minimum spanning tree prim+kruskal
- LeetCode · 23. Merge K ascending linked lists · recursion · iteration
- NEOVIM下载安装与配置
- MySQL压缩包方式安装,傻瓜式教学
- (7/29)基础板子最小生成树prim+kruskal
- Qt 同时生成动态库和静态库
- Google Earth Engine ——我们如何筛选一个列表中的排序以时间为例
- DistSQL in-depth analysis: creating a dynamic distributed database
- 走进Redis,让你重新认识redis。绝不是表面
- socket:内核初始化及创建流(文件)详细过程
猜你喜欢
随机推荐
mysql remove duplicate data
Deep Kalman Filter Network for Video Compression Artifact Removal
IDEA 连接 数据库
系统结构考点之CRAY-1向量处理机
MySQL 8.0.29 decompressed version installation tutorial (valid for personal testing)
Teach you how to build a permanently running personal server
系统结构考点之多级混洗交换网络
MySql 5.7.38下载安装教程 ,并实现在Navicat操作MySql
Apache DolphinScheduler新一代分布式工作流任务调度平台实战-
【菜鸡含泪总结】如何用pip、anaconda安装库
冲刺第六周
[Deep Learning] Understanding of Domain Adaptation in Transfer Learning and Introduction of 3 Techniques
Generate OOM records in a production environment. Conclusion: Don't be lazy to query useless fields unless you are completely sure.
nVisual网络可视化管理平台功能和价值点
基于ABP实现DDD--领域服务、应用服务和DTO实践
MySQL分页查询的5种方法
Google Earth Engine ——ee.List.sequence函数的使用
Navigation Bar----Personal Center Dropdown
MySQL user authorization
HCIP第十六天