华为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思路代码 题目描述 给出一个二叉树如下图所示: 6/ \7 9\ / -2 6 请由该二叉树生成一个新的二叉树,它满足其树中的每个节点将包含原始树中的左子树和右子树的和。 20 (7-296)/ \-2 6\ / 0 0 左子树…...

技术爱好者完全用台式机部件定制游戏笔记本电脑
高端笔记本电脑的功能强大到令人难以置信的地步,但大多数笔记本电脑在至少几个关键性能方面仍然落后于台式机。一位 YouTuber 对这种情况感到厌倦,为了抹除这种差距,他开始了为期 14 个月的旅程,使用真正的台式机硬件打造自己的笔…...
100个练习学习Rust!if・Panic・演练
之前的文章 【0】准备 【1】构文・整数・变量 ← 上回 【2】 if・Panic・演练 ← 本次 这是“100 Exercise To Learn Rust”的第2次练习!本次的主题包括 if 表达式、panic 机制,以及对前面内容的总结练习。 本次相关的页面如下: 2.3. Bran…...

MODELSIM仿真报错解决记录
目录 问题:Modelsim报错:Error (10228): Verilog HDL error at Line_Shift_RAM_1Bit.v(39): module “Line_Shift_RAM_1 原因:创建的IP核放到了别的位置 解决方法:删掉IP核以及QIP等文件,将IP核创建到工程目录下 问…...
day33-负载均衡实战
01.问题总结 1.rsync同步注意目录加/和不加/的区别 2.安装wordpress过程中禁止使用IP安装,解析成域名安装 比如安装过程 10.0.0.7--->填写数据库信息--->写入数据库中 如果安装完成后再使用www.wp.com访问,不能访问页面乱码的问题。 3.挂载wordpress挂载uplo…...
网络接口 eno1 未连接或未托管
网络接口 eno1 未连接或未托管,通常意味着该接口没有被识别或没有被配置为自动连接到网络。以下是一些可能的解决方案: 检查物理连接: 确保您的以太网电缆正确连接到 eno1 接口和调制解调器/路由器。 启用网络接口: 使用以下命令…...

Linux I/O 多路复用机制详解
文章目录 1 文件描述符(File Descriptor)1.1 什么是文件描述符?1.2 文件描述符与文件的关系 2 文件描述符集合(File Descriptor Set)2.1 什么是文件描述符集合?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. 二叉树(重点) 2.1 概念 2.2 二叉树的性质 2.3 二叉树的存储 2.4 二叉树的遍历 前中后序遍历 层序遍历: 2.5二叉树的基本操作 本篇主要理解树和二叉树相关概念,二叉树遍…...
使用duplicate搭建备库或者级联备库
使用duplicate搭建备库或者级联备库: 主库或者源端: 1. 创建pfile,更改&添加部分参数、传输到备库; 2. 主库(或者源端)的tnsnames.ora文件添加 备库的连接信息 备库: 1. 备库添加静态监听 2…...

【存储学习笔记】4:快照(Snapshot)技术的实现方式
1 快照 1.1 动机 在上一篇《备份》里提到,热备份就是在执行操作时,服务器需要正常处理来自用户或应用对数据的更新,这样能够保证数据7*24小时可用(在很多服务里这是必要的)。 而热备份的困难就是如何保证数据的一致…...
数根(字符串数根公式)
公式:a的数根(a-1)%91; #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)
📣📣📣📣📣📣📣📣 ✏️作者主页:枫霜剑客 📋 系列专栏:C语言知识学习归纳总结(逐梦篇专栏合集) 🌲上一篇: C语…...
【微服务架构实战】结合实际案例进行微服务架构的设计与实现
微服务架构实战 结合实际案例进行微服务架构的设计与实现 引言 微服务架构(Microservices Architecture)是一种将大型应用程序拆分成一组小型、独立的服务的方法,每个服务都专注于特定的业务功能,并能够独立开发、部署和扩展。这…...
为什么要有二级指针
提示:文章 文章目录 前言一、背景二、 2.1 2.2 总结 前言 前期疑问: 本文目标: 一、背景 之前一直疑问为什么要有二级指针,一直没有写这个帖子,今天整理了一下,收获颇丰 二、 2.1 // 增加对二级指针…...

如何保证数据不丢失?(死信队列)
死信队列 1、什么是死信 死信通常是消息在特定的场景下表现: 消息被拒绝访问消费者发生异常,超过重试次数消息的Expiration过期时长或者队列TTL过期时间消息队列到达最大容量 maxLength 2、什么是死信队列 只由死信构成的消息队列是死信队列 死信队…...

树莓派开发笔记01-树莓派的系统烧录以及初次开机配置
github主页:https://github.com/snqx-lqh gitee主页:https://gitee.com/snqx-lqh 本项目github地址:https://github.com/snqx-lqh/RaspberryPiLearningNotes 本项目gitee地址:https://gitee.com/snqx-lqh/RaspberryPiLearningNote…...

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

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...

【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...

路由基础-路由表
本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中,往往存在多个不同的IP网段,数据在不同的IP网段之间交互是需要借助三层设备的,这些设备具备路由能力,能够实现数据的跨网段转发。 路由是数据通信网络中最基…...

【QT控件】显示类控件
目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏:QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...

World-writable config file /etc/mysql/mysql.conf.d/my.cnf is ignored
https://stackoverflow.com/questions/53741107/mysql-in-docker-on-ubuntu-warning-world-writable-config-file-is-ignored 修改权限 -> 重启mysql # 检查字符集配置 SHOW VARIABLES WHERE Variable_name IN (character_set_server, character_set_database ); --------…...