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

中后序遍历构建二叉树与应用I

目录

题目描述

思路分析

AC代码


题目描述

按中序遍历和后序遍历给出一棵二叉树,求这棵二叉树中叶子节点权值的最小值。

输入保证叶子节点的权值各不相同。

输入

测试数据有多组
对于每组测试数据,首先输入一个整数N (1 <= N <= 10000),代表二叉树有N个节点,接下来的一行输入这棵二叉树中序遍历的结果,最后一行输入这棵二叉树后序遍历的结果
输入一直处理到文件尾(EOF)

输出

对于每组测试数据,输出一个整数,代表二叉树中叶子节点权值最小值

输入样例1

7
3 2 1 4 5 7 6
3 1 2 5 6 7 4
8
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
1
255
255

输出样例1

1
3
255

思路分析

是要找出权值最小的叶子节点。

首先根据中序和后序遍历找出叶子节点。

因为叶子节点是没有左子树和右子树的节点,所以根据后序找出根节点,根据中序找出根节点的左右子树,这里使用递归,发现左右都是空的节点就是叶子节点,再用一个min变量找出最小的即可。

注意输入多组数据。

AC代码

#include<iostream>using namespace std;bool recursion(int *postorder, int *inorder, int last,int&min) {if (last < 0)return true;int root = 0;for (int i = 0; i <= last; i++)if (inorder[i] == postorder[last]) {root = i;break;}if(recursion(postorder, inorder, root - 1,min)&&recursion(postorder + root, inorder + root + 1, last - root - 1,min)){if(min>postorder[root])min=postorder[root];return true;}return false;
}int main() {int size;while (cin >> size){int postorder[size], inorder[size];for (int i = 0; i < size; i++)cin >> inorder[i];for (int i = 0; i < size; i++)cin >> postorder[i];int min=0x3f3f3f3f;recursion(postorder, inorder, size - 1,min);cout<<min<<endl;}
}

相关文章:

中后序遍历构建二叉树与应用I

目录 题目描述 思路分析 AC代码 题目描述 按中序遍历和后序遍历给出一棵二叉树&#xff0c;求这棵二叉树中叶子节点权值的最小值。 输入保证叶子节点的权值各不相同。 输入 测试数据有多组 对于每组测试数据&#xff0c;首先输入一个整数N (1 < N < 10000)&#x…...

随机退化模型--基础篇(1)

随机退化模型--基础篇(1) 1. 随机退化建模1.1 瞬间失效1.2 存在缓慢退化过程的失效2. 通俗解释2.1 包引入2.2 参数定义2.3 基于递归函数的更新2.4 结果可视化1. 随机退化建模 随机模型亦称“非确定的、概率的模型”,是按随机变量建立的模型。其特点是; 模型参数、模拟对象发…...

2023.2.15工作学习记录 git Docker compose容器编排

关于Git错误提交了target目录 是因为在ignore目录中没有加入biz这个工程 以后提交代码时一定要检查好自己提交的代码 首先把所有的全部取消 然后再根据自己要提交的内容一个个来勾选 Docker网络 container模式&#xff1a;新建的容器和已经存在的一个容器共享一个网络…...

基于jeecgboot的flowable流程增加节点自动跳过功能

为了满足有时候需要在某个节点没有人员处理的时候需要自动跳过&#xff0c;所以增加了这个功能。 一、FlowComment意见里增加一个类型8&#xff0c;跳过流程 /** * 流程意见类型 * */ public enum FlowComment { /** * 说明 */ NORMAL("1", "…...

流程引擎之Activiti简介

背景Activiti 是一个开源架构的工作流引擎&#xff0c;基于 bpmn2.0 标准进行流程定义&#xff0c;其前身是 jBPM&#xff0c;Activiti 相对于 jBPM 更轻量&#xff0c;更易上手&#xff0c;且天然集成了 Spring。2010年 jBPM 创始人 Tom Baeyens 离开 JBoss&#xff0c;随之加…...

4.打包子应用 投票

接上回 最终得到这样的目录 mysite/manage.pymysite/__init__.pysettings.pyurls.pyasgi.pywsgi.pypolls/__init__.pyadmin.pyapps.pymigrations/__init__.py0001_initial.pymodels.pystatic/polls/images/background.gifstyle.csstemplates/polls/detail.htmlindex.htmlresult…...

华为OD机试 - 服务依赖(JavaScript) | 机试题算法思路 【2023】

服务依赖 题目 在某系统中有众多服务,每个服务用字符串(只包含字母和数字,长度<=10)唯一标识,服务间可能有依赖关系,如A依赖B,则当B故障时导致A也故障。 传递具有依赖性,如A依赖B,B依赖C,当C故障时导致B故障,也导致A故障。给出所有依赖关系以及当前已知故障服务…...

目标检测综述(一份全的自制PPT): 涵盖各种模型简介对比,适合入门和了解目标检测现状

[TOC](目标检测综述(一份全的自制PPT): 涵盖各种模型简介对比&#xff0c;适合入门和了解目标检测现状) 注&#xff1a;本文仅供学习&#xff0c;未经同意勿转。分享的PPT请勿二次传播&#xff0c;或者用于其他商用途径。若使用本文PPT请注明来源&#xff0c;感谢配合 前言&…...

Vulnhub-DC-2实战靶场

Vulnhub-DC-2实战靶场 https://blog.csdn.net/ierciyuan/article/details/127560871 这次试试DC-2&#xff0c;目标是找到官方设置的5个flag。 一. 环境搭建 1. 准备工具 虚拟机Kali&#xff1a; 自备&#xff0c;我的kali的IP为192.168.3.129 靶场机&#xff1a; https…...

从输入URL到渲染的过程中到底发生了什么?

CDN缓存DNSTCP三次握手、四次挥手浏览器渲染过程输入URL到页面渲染过程的一些优化 下面我将“从输入URL到渲染的全过程”大概的描述出来&#xff0c;再对其过程加以解释&#xff0c;了解过程中可以做哪些优化。文章内容有点长&#xff0c;需要有足够的耐心看完哟&#xff01;&…...

旋转屏幕导致 Fragment 中的 onConfigurationChanged 被调用两次

环境 IDE Android Studio Dolphin 2021.3.1&#xff1b; 项目配置 Android Gradle plugin version: 7.1.3 Gradle Version: 7.2 Gradle JDK: 11 Compile Sdk Version: 32 问题描述 项目使用的 Bottom Navigation Activity 基本结构&#xff0c;在调试程序时发现&#xff0c…...

23年校招DL/NLP/推荐系统/ML/算法基础面试必看300问及答案

2020年校招已经开始了&#xff0c;在疫情全球肆虐的背景下&#xff0c;全球就业情况异常艰难&#xff0c;加上美国对中国企业打压持续升级&#xff0c;对于马上开始秋招找工作的毕业生而言&#xff0c;更是难上加难。我们不能凭一己之力改变现状&#xff0c;但我们可以凭借自己…...

Python基础知识汇总(字符串二)

目录 检索字符串 count()方法 find()方法 in关键字 index()方法 rindex()方法 startswith()方法...

【FPGA】Verilog:实现十六进制七段数码管显示 | 7-Segment Display

写在前面&#xff1a;本章主要内容为理解七点数码管显示的概念&#xff0c;并使用 Verilog 实现。生成输入信号后通过仿真确认各门的动作&#xff0c;通过 FPGA 检查在 Verilog 中实现的电路的操作。 Ⅰ. 前置知识 七段数码管是利用多重输出功能的非常有用的元件。该元件用于字…...

Android开发:Activity启动模式

1.怎样设置Activity的启动模式 可以在清单文件中自己添加活动的启动模式, android : launchMode"standard", 不写的话系统默认就是标准模式. 2.启动模式 2.1.默认启动模式 标准启动模式就是栈, 打开一个活动就将活动压入栈中, 返回就将活动退出栈中. 不同的Activit…...

01_Docker 简介

01_Docker 简介 文章目录01_Docker 简介1.1 Docker 简介1.2 Docker 组件1.2.1 Docker 客户端和服务区1.2.2 Docker 镜像1.2.3 Registry1.2.4 Docker 容器参考资料https://www.runoob.com/docker/ubuntu-docker-install.html 1.1 Docker 简介 Docker 是一个能够把开发的应用程…...

一文精通MVCC机制

MVCC(Multi-Version Concurrency Control)多版本并发控制机制使用串行化隔离级别时&#xff0c;mysql会将所有的操作加锁互斥&#xff0c;来保证并发安全。这种方式必然降低并发性能。mysql在读已提交和可重复读隔离级别下&#xff0c;对一行数据的读和写两个操作默认是不会通过…...

商用ESP32协议采集器源码分享开篇

这是一个关于chatGPT帮助嵌入式程序员开发商业项目的故事. 在开发这个项目的过程中,chatGPT发布了,在它的帮助下,项目开发量减少了10%,所以这个专栏,既是一个关于Micropython开发ESP32的专栏,也是一个程序员在AI的帮助下,提升效率,加速挣钱的案例. 看完之后,你将知道如何用mic…...

代码随想录算法训练营第三十四天 | 860.柠檬水找零,406.根据身高重建队列,452. 用最少数量的箭引爆气球

一、参考资料柠檬水找零https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html 根据身高重建队列 https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html 用最少数量的箭引爆气球ht…...

DDR4介绍01

DDR4&#xff08;第四代双倍数据率同步动态随机存储器SDRAM&#xff09; 关于内存方面知识&#xff0c;大部分人、包括我自己也不是很懂&#xff0c;希望此篇文章能起到点作用&#xff0c;做硬件的就得把相关专业知识学牢了&#xff0c;尤其是专业术语。 下面是DDR4知识做一次…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

32位寻址与64位寻址

32位寻址与64位寻址 32位寻址是什么&#xff1f; 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元&#xff08;地址&#xff09;&#xff0c;其核心含义与能力如下&#xff1a; 1. 核心定义 地址位宽&#xff1a;CPU或内存控制器用32位…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...

SQL进阶之旅 Day 22:批处理与游标优化

【SQL进阶之旅 Day 22】批处理与游标优化 文章简述&#xff08;300字左右&#xff09; 在数据库开发中&#xff0c;面对大量数据的处理任务时&#xff0c;单条SQL语句往往无法满足性能需求。本篇文章聚焦“批处理与游标优化”&#xff0c;深入探讨如何通过批量操作和游标技术提…...

Qt的学习(二)

1. 创建Hello Word 两种方式&#xff0c;实现helloworld&#xff1a; 1.通过图形化的方式&#xff0c;在界面上创建出一个控件&#xff0c;显示helloworld 2.通过纯代码的方式&#xff0c;通过编写代码&#xff0c;在界面上创建控件&#xff0c; 显示hello world&#xff1b; …...