当前位置: 首页 > news >正文

华为od(D卷)二叉树计算

文章目录

  • 题目描述
  • 输入描述
  • 输出描述
  • 示例1
  • 思路
  • 代码

题目描述

给出一个二叉树如下图所示:

     6/ \7   9\  /  -2 6  

请由该二叉树生成一个新的二叉树,它满足其树中的每个节点将包含原始树中的左子树和右子树的和。

      20 (7-2+9+6)/   \-2    6\   /  0  0 

左子树表示该节点左侧叶子节点为根节点的一颗新树;右子树表示该节点右侧叶子节点为根节点的一颗新树

输入描述

2行整数,
第1行表示二叉树的中序遍历,
第2行表示二叉树的前序遍历,以空格分割

例如:

7 -2 6 6 9
6 7 -2 9 6

输出描述

1行整数,表示求和树的中序遍历,以空格分割

例如:

输出1 -2 0 20 0 6

示例1

输入:
-3 12 6 8 9 -10 -7
8 12 -3 6 -10 9 -7

输出:
0 3 0 7 0 2 0

思路

1 . 前序中序构造二叉树

前序: 中左右; 判断“中”是第一个元素。
中序: 根据前序找到的“中” ,判断左右子树是谁。(此时可以提前计算左右子树的和)

代码

public class Demo11 {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 中序int[] in = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();// 前序int[] pre = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();// 最终中序结果int[] resMid = new int[in.length];buildTree(pre, in, resMid, 0, pre.length, 0, in.length);System.out.println(Arrays.toString(resMid));scanner.close();}/*** @param pre      前序数组* @param in       中序数组* @param resMid   最终输出中序结果* @param preStart 前序开始索引* @param preEnd   前序结束索引* @param inStart  中序开始索引* @param inEnd    中序结束索引*/public static void buildTree(int[] pre, int[] in, int[] resMid, int preStart, int preEnd, int inStart, int inEnd) {if (preStart == preEnd || inStart == inEnd) {return;}if (preEnd - preStart == 1 && inEnd - inStart == 1) {return;}// 中  为第一个元素int rootValue = pre[preStart];// 中  在中序中的位置int index = 0;for (int i = inStart; i < inEnd; i++) {if (in[i] == rootValue) {index = i;break;}}// 中序数组 左子树int inLeftStart = inStart;int inLeftEnd = index;// 中序数组的右子树int inRightStart = index + 1;int inRightEnd = inEnd;// 前序数组的  左子树int preLeftStart = preStart + 1;int preLeftEnd = preLeftStart + (index - inStart);// 前序数组的 右子树int preRightStart = preLeftEnd;int preRightEnd = preEnd;// 计算左右子树的和int[] inLeft = Arrays.copyOfRange(in, inLeftStart, inLeftEnd);int[] inRight = Arrays.copyOfRange(in, inRightStart, inRightEnd);resMid[index] = Arrays.stream(inLeft).sum() +Arrays.stream(inRight).sum();// 递归buildTree(pre, in, resMid, preLeftStart, preLeftEnd, inLeftStart, inLeftEnd);buildTree(pre, in, resMid, preRightStart, preRightEnd, inRightStart, inRightEnd);}
}

相关文章:

华为od(D卷)二叉树计算

文章目录 题目描述输入描述输出描述示例1思路代码 题目描述 给出一个二叉树如下图所示&#xff1a; 6/ \7 9\ / -2 6 请由该二叉树生成一个新的二叉树&#xff0c;它满足其树中的每个节点将包含原始树中的左子树和右子树的和。 20 (7-296)/ \-2 6\ / 0 0 左子树…...

技术爱好者完全用台式机部件定制游戏笔记本电脑

高端笔记本电脑的功能强大到令人难以置信的地步&#xff0c;但大多数笔记本电脑在至少几个关键性能方面仍然落后于台式机。一位 YouTuber 对这种情况感到厌倦&#xff0c;为了抹除这种差距&#xff0c;他开始了为期 14 个月的旅程&#xff0c;使用真正的台式机硬件打造自己的笔…...

100个练习学习Rust!if・Panic・演练

之前的文章 【0】准备 【1】构文・整数・变量 ← 上回 【2】 if・Panic・演练 ← 本次 这是“100 Exercise To Learn Rust”的第2次练习&#xff01;本次的主题包括 if 表达式、panic 机制&#xff0c;以及对前面内容的总结练习。 本次相关的页面如下&#xff1a; 2.3. Bran…...

MODELSIM仿真报错解决记录

目录 问题&#xff1a;Modelsim报错&#xff1a;Error (10228): Verilog HDL error at Line_Shift_RAM_1Bit.v(39): module “Line_Shift_RAM_1 原因&#xff1a;创建的IP核放到了别的位置 解决方法&#xff1a;删掉IP核以及QIP等文件&#xff0c;将IP核创建到工程目录下 问…...

day33-负载均衡实战

01.问题总结 1.rsync同步注意目录加/和不加/的区别 2.安装wordpress过程中禁止使用IP安装,解析成域名安装 比如安装过程 10.0.0.7--->填写数据库信息--->写入数据库中 如果安装完成后再使用www.wp.com访问&#xff0c;不能访问页面乱码的问题。 3.挂载wordpress挂载uplo…...

网络接口 eno1 未连接或未托管

网络接口 eno1 未连接或未托管&#xff0c;通常意味着该接口没有被识别或没有被配置为自动连接到网络。以下是一些可能的解决方案&#xff1a; 检查物理连接&#xff1a; 确保您的以太网电缆正确连接到 eno1 接口和调制解调器/路由器。 启用网络接口&#xff1a; 使用以下命令…...

Linux I/O 多路复用机制详解

文章目录 1 文件描述符&#xff08;File Descriptor&#xff09;1.1 什么是文件描述符&#xff1f;1.2 文件描述符与文件的关系 2 文件描述符集合&#xff08;File Descriptor Set&#xff09;2.1 什么是文件描述符集合&#xff1f;2.2 fd_set 结构体 3 select() 函数的工作原理…...

第43课 Scratch入门篇:雪花随风飘

雪花随风飘 故事背景: 雪花轻轻地从灰蒙蒙的天空中飘落下来,它们像是天空中飘洒下来的羽毛,又像是冬日的精灵在翩翩起舞。每一片雪花都独一无二,它们在空中旋转、飘荡,最终缓缓降落在屋顶、树枝、街道和行人的肩头。 程序原理: 众多的雪花肯定是克隆功能,降落过程是通过…...

VueUse 基于 Vue 3 Composition API 的高质量 Hooks 库

VueUse 是什么? VueUse 是基于 Vue 3 Composition API 的高质量 Hooks 库。例如获取滚动的距离 VueUse 官网:VueUse | VueUse VueUse 什么使用? 1、通过npm安装 VueUse npm i @vueuse/core 2、搜索需要使用的函数,例如搜索 useScroll 滚动 3、使用useScroll 滚动函数 …...

ARM CoreLink 系列 5.1.1 -- CI-700 System Address Map 】

文章目录 System Address MapRN SAMRN SAM memory regions and target typesSAM memory region size configurationRN SAM target ID selectionSystem Address Map 所有的CHI 命令都包含一个 Source ID 和 Target ID, 其中 Source ID 可以来自于 RN Node, Target ID 可以来自…...

【数据结构】二叉树(一)

目录 1. 树型结构 概念 树的表示形式 ​编辑 2. 二叉树&#xff08;重点&#xff09; 2.1 概念 2.2 二叉树的性质 2.3 二叉树的存储 2.4 二叉树的遍历 前中后序遍历 层序遍历&#xff1a; 2.5二叉树的基本操作 本篇主要理解树和二叉树相关概念&#xff0c;二叉树遍…...

使用duplicate搭建备库或者级联备库

使用duplicate搭建备库或者级联备库&#xff1a; 主库或者源端&#xff1a; 1. 创建pfile&#xff0c;更改&添加部分参数、传输到备库&#xff1b; 2. 主库&#xff08;或者源端&#xff09;的tnsnames.ora文件添加 备库的连接信息 备库&#xff1a; 1. 备库添加静态监听 2…...

【存储学习笔记】4:快照(Snapshot)技术的实现方式

1 快照 1.1 动机 在上一篇《备份》里提到&#xff0c;热备份就是在执行操作时&#xff0c;服务器需要正常处理来自用户或应用对数据的更新&#xff0c;这样能够保证数据7*24小时可用&#xff08;在很多服务里这是必要的&#xff09;。 而热备份的困难就是如何保证数据的一致…...

数根(字符串数根公式)

公式&#xff1a;a的数根(a-1)%91&#xff1b; #include <bits/stdc.h> using namespace std; string s; long long sum; int main(){cin>>s;for(int i0;i<s.size();i){sums[i]-0;}cout<<(sum-1)%91; }...

C语言之文件操作上卷(二十一)(逆行人生-2024)

&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3; ✏️作者主页&#xff1a;枫霜剑客 &#x1f4cb; 系列专栏&#xff1a;C语言知识学习归纳总结&#xff08;逐梦篇专栏合集&#xff09; &#x1f332;上一篇: C语…...

【微服务架构实战】结合实际案例进行微服务架构的设计与实现

微服务架构实战 结合实际案例进行微服务架构的设计与实现 引言 微服务架构&#xff08;Microservices Architecture&#xff09;是一种将大型应用程序拆分成一组小型、独立的服务的方法&#xff0c;每个服务都专注于特定的业务功能&#xff0c;并能够独立开发、部署和扩展。这…...

为什么要有二级指针

提示&#xff1a;文章 文章目录 前言一、背景二、 2.1 2.2 总结 前言 前期疑问&#xff1a; 本文目标&#xff1a; 一、背景 之前一直疑问为什么要有二级指针&#xff0c;一直没有写这个帖子&#xff0c;今天整理了一下&#xff0c;收获颇丰 二、 2.1 // 增加对二级指针…...

如何保证数据不丢失?(死信队列)

死信队列 1、什么是死信 死信通常是消息在特定的场景下表现&#xff1a; 消息被拒绝访问消费者发生异常&#xff0c;超过重试次数消息的Expiration过期时长或者队列TTL过期时间消息队列到达最大容量 maxLength 2、什么是死信队列 只由死信构成的消息队列是死信队列 死信队…...

树莓派开发笔记01-树莓派的系统烧录以及初次开机配置

github主页&#xff1a;https://github.com/snqx-lqh gitee主页&#xff1a;https://gitee.com/snqx-lqh 本项目github地址&#xff1a;https://github.com/snqx-lqh/RaspberryPiLearningNotes 本项目gitee地址&#xff1a;https://gitee.com/snqx-lqh/RaspberryPiLearningNote…...

微信答题小程序产品研发-后端开发

在开发答题小程序的后端服务和数据库设计时&#xff0c;需要考虑API的设计、数据库模型的构建以及数据的安全性和一致性。 这里我采用了云开发&#xff0c;后端语言是Node&#xff0c;数据库是NoSql&#xff0c;然后我简单整理了各个功能模块的后端开发概要和数据库设计。 1. …...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...