首页 > 其他分享 >1099 构建二叉搜索树

1099 构建二叉搜索树

时间:2023-04-21 20:23:28浏览次数:43  
标签:结点 idx int 1099 dfs 二叉 构建 include

二叉搜索树 (BST) 递归定义为具有以下属性的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值
  • 它的左、右子树也分别为二叉搜索树

给定二叉树的具体结构以及一系列不同的整数,只有一种方法可以将这些数填充到树中,以使结果树满足 BST 的定义。

请你输出结果树的层序遍历。

示例如图 1 和图 2 所示。

24c2521f-aaed-4ef4-bac8-3ff562d80a1b.jpg

输入格式

第一行包含一个正整数 N,表示树的结点个数。

所有结点的编号为 0∼N−1,并且编号为 0 的结点是根结点。

接下来 N 行,第 i 行(从 0 计数)包含结点 i 的左右子结点编号。如果该结点的某个子结点不存在,则用 −1 表示。

最后一行,包含 N 个不同的整数,表示要插入树中的数值。

输出格式

输出结果树的层序遍历序列。

数据范围

1≤N≤100

输入样例:

9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42

输出样例:

58 25 82 11 38 67 45 73 42

代码实现:

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=105;
int l[N],r[N],res[N],a[N],cnt,idx;
void dfs(int idx){
    if(l[idx]!=-1)dfs(l[idx]);
    res[idx]=a[cnt++];
    if(r[idx]!=-1)dfs(r[idx]);
}
void bfs(int x){
    queue<int>q;
    q.push(x);
    while(q.size()){
        int t=q.front();
        q.pop();
        if(!idx)cout<<res[t];
        else cout<<" "<<res[t];
        idx++;
        if(l[t]!=-1)q.push(l[t]);
        if(r[t]!=-1)q.push(r[t]);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>l[i]>>r[i];
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    dfs(0);
    bfs(0);
    return 0;
}

 

标签:结点,idx,int,1099,dfs,二叉,构建,include
From: https://www.cnblogs.com/hxss/p/17341689.html

相关文章

  • 1102 反转二叉树
    以下是来自 MaxHowell@twitter 的内容:谷歌:我们的百分之九十的工程师都使用你编写的软件,但是你连在白板上反转二叉树都做不到,还是滚吧。现在,请你证明你会反转二叉树。输入格式第一行包含一个整数 N,表示树的结点数量。所有结点编号从 0 到 N−1。接下来 N 行,每行对......
  • 1、Pipeline Job的简单构建与代码片断生成器
    PipelineJob脚本式语法和声明式语法Jenkins2.x支持两种pipeline语法:脚本式语法和声明式语法脚本式流水线://脚本式流水线:node用于脚本式流水线,从技术层面上来说,//它是一个步骤,代表可以用于流水线中执行活动的资源node('node01'){stages{stage('Build'){steps......
  • 如何构建适合自己的DevOps软件测试改进方案
    ​根据2022年的DevOps全球调查报告显示,主流软件企业采用或部分采用DevOps且已获得良好成效的占比已达70%,DevOps俨然成为当下软件开发研究的重要方向。测试作为软件开发的必要过程,是提升软件可靠性、保证软件质量的关键环节。然而,从过往研究文献来看,希望通过DevOps提升软件交付效......
  • ORB305与CISCO路由器构建L2TP over IPSec VPN操作手册
    1、网络拓扑在思科路由器与ORB305之间建立一个安全隧道,对客户路由器端设备子网,与思科路由器端服务器子网之间的数据流进行安全保护,组网拓扑图如图所示。2、思科路由器端配置指导(此处以多数客户使用专线上网形式为例)Cisco(AR1)配置配置1.AAA配置aaanew-model//启用AAAaaaaut......
  • 开源构建系统Buck2发布
    看来最近Meta的工程师是一点都没有闲着,前两天刚开源AI图像分割模型,这不就又发布了名为Buck2的开源构建系统。Buck2是一个已经在Meta内部使用了一段时间的大型构建系统,目前Meta有数千名开发人员正在使用该构建系统,每天执行数百万次的构建。在Meta的内部测试中......
  • 开源构建系统Buck2发布
    看来最近Meta的工程师是一点都没有闲着,前两天刚开源AI图像分割模型,这不就又发布了名为Buck2的开源构建系统。Buck2是一个已经在Meta内部使用了一段时间的大型构建系统,目前Meta有数千名开发人员正在使用该构建系统,每天执行数百万次的构建。在Meta的内部测试中......
  • 开源构建系统Buck2发布
    看来最近Meta的工程师是一点都没有闲着,前两天刚开源AI图像分割模型,这不就又发布了名为Buck2的开源构建系统。Buck2是一个已经在Meta内部使用了一段时间的大型构建系统,目前Meta有数千名开发人员正在使用该构建系统,每天执行数百万次的构建。在Meta的内部测试中......
  • 数据结构 ---> 二叉树 -->堆之解析_01
    老友们好!本期将对堆之构建进行解说!相信,初学此章节的老友!!或多或少,对前一期的部分代码,有所困惑!说真的,堆的有些内容理解起来还是挺困难的!好了,废话不多讲!开始本期的解析之旅吧!希望大家都能有所收获!!下面,先看一组,上一期的图示:>那么该如何操作,才能取得前几名的数值呢?针对这点,部分老友......
  • 什么配置的电脑可满足基因组索引构建的需求?
    经常有朋友问起自己要做什么分析,推荐一个电脑的配置。通常限制程序运行的最主要因素是内存,内存不足程序会直接运行不起来,CPU性能弱顶多是运行的慢,硬盘比较便宜,不需要特别评估。针对这个问题,我们准备推出一系列测试推文,统计计算常用软件的运行时间、所需的最大物理内存(后面统计的都......
  • 如何使用Webpack工具构建项目
    起步webpack用于编译JavaScript模块。一旦完成 安装,你就可以通过webpack CLI 或 API 与其配合交互。如果你还不熟悉webpack,请阅读 核心概念 和 对比,了解为什么要使用webpack,而不是社区中的其他工具。运行webpack5的Node.js最低版本是10.13.0(LTS)。基本......