1099 Build A Binary Search Tree (30 分)【难度: 一般 / 知识点: 建立二叉搜索树】
2023-09-11 14:15:52 时间
https://pintia.cn/problem-sets/994805342720868352/problems/994805367987355648
首先: 要知道二叉搜索树的中序遍历是有序的
故可以将数组先排序,然后按照中序遍历,遍历树并给树赋值。最后层序遍历输出即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
unordered_map<int,int>l,r;
int n,a[N],idx,ans[N];
void dfs(int u)
{
if(l[u]!=-1) dfs(l[u]);
ans[u]=a[idx++];
if(r[u]!=-1) dfs(r[u]);
}
void print()
{
queue<int>q; q.push(0);
vector<int>ve;
while(q.size())
{
int t=q.front(); q.pop();
ve.push_back(ans[t]);
if(l[t]!=-1) q.push(l[t]);
if(r[t]!=-1) q.push(r[t]);
}
for(int i=0;i<ve.size();i++)
{
if(i) cout<<" ";
cout<<ve[i];
}
}
int main(void)
{
cin>>n;
for(int i=0;i<n;i++)
{
int id1,id2; cin>>id1>>id2;
l[i]=id1,r[i]=id2;
}
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
dfs(0);
print();
return 0;
}
相关文章
- Java实现 LeetCode 688 “马”在棋盘上的概率(DFS+记忆化搜索)
- 顶部搜索框背景色渐变
- Android特效专辑(九)——仿微信雷达搜索好友特效,逻辑清晰实现简单
- 搜索引擎系列 ---lucene简介 创建索引和搜索初步
- 8-crm项目-kingadmin,列表页---搜索
- RestfulApi 学习笔记——查询与过滤还有搜索(五)
- Open3D 点云的圆柱形邻域搜索
- Java爬虫搜索原理实现
- SAP CRM的WITH_INDOBJECTS搜索参数问题
- SAP CRM Fiori搜索没有命中情况下的调试细节
- atitit 方便搜索的文档文章结构框架.docx 目录 1.1. 三种搜索模式 tree hash关键词模式 关联搜索,对应的三种索引1 1.2. 好的标题规范与副标题1 1.3. Tr
- Atitit btree 搜索原理 目录 第一节 左边小右边大 的有序树1 第二节 平衡算法1 第三节 层次高度一般3--4层3 第四节 类似索引3 第二章 Ref5 第一节 左边小右
- 智能优化算法:回溯搜索优化算法-附代码
- C# 百度搜索结果xpath分析
- [LeetCode] 538. 把二叉搜索树转换为累加树 ☆(中序遍历变形)