华为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. …...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...

倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...