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

P1827 [USACO3.4] 美国血统 American Heritage(前序 + 中序 生成后序)

P1827 [USACO3.4] 美国血统 American Heritage(前序 + 中序 生成后序)

一、前言

二叉树入门题。涉及到树的基本知识、树的结构、树的生成。
本文从会从结构,到完成到,优化。

二、基础知识

Ⅰ、二叉树的遍历

  • 前序遍历: 左右
  • 中序遍历:
  • 后序遍历: 左右

通过上面的观察,可得根在那,就是什么方式的遍历

Ⅱ、二叉树的结构

二叉树的结构:节点值 + 左节点指针 + 右节点指针

// c++的结构体写法
struct node {char val;node *left;node *right;node() : val(0), left(nullptr), right(nullptr){}node(int val) : val(val), left(nullptr), right(nullptr){}node(int val, node *left, node *right) : val(val), left(left), right(right){}
};
// c语言结构体写法
struct node {char val;struct node *left;struct node *right;node() : val(0), left(NULL), right(NULL){}node(int val){val = val;left = NULL;right = NULL;{node(int val, struct node *left, struct node *right) {val = val;left = left;right = right;}
};

三、直接思路

通过 前序 + 中序 直接生成 树。然后再前序遍历(可以过)
现在的问题,就变成了。怎么生成树了。
估计大家在学习数据结构,二叉树这一章节中。老师肯定讲过手写这个题(通过前序或后序找到根节点,然后把中序分成两部分,左子树,右子树)。但是现在怎么把他变成代码呢?

#include <iostream>
using namespace std;struct node {char val;node *left;node *right;node() : val(0), left(nullptr), right(nullptr){}node(char x) : val(x), left(nullptr), right(nullptr){}node(char x, node *left, node *right) : val(x), left(left), right(right){}
};
/*
s1 中序
[inorderBegin, inorderEnd)
s2 前序
[preorderBegin, preorderEnd)
上述就是现在树的范围
再分割子树的范围就可以了
明白范围!!!左端点可取,右端点不可取
*/
node *traversal(string s1, int inorderBegin, int inorderEnd, string s2, int preorderBegin, int preorderEnd) {if (preorderEnd == preorderBegin) return nullptr;char val = s2[preorderBegin];node *root = new node(val);if (preorderEnd - preorderBegin == 1) return root;int delimiterIndex; // 左右子树的分割点for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (s1[delimiterIndex] == val) break;}// 左子树// 中序int leftInorderBegin = inorderBegin;int leftInorderEnd = delimiterIndex;// 前序int leftPreorderBegin = preorderBegin + 1;int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;// 右子树int rightInorderBegin = delimiterIndex + 1;int rightInorderEnd = inorderEnd;int rightPreorderBegin = preorderBegin + delimiterIndex - inorderBegin + 1;int rightPreorderEnd = preorderEnd;root->left = traversal(s1, leftInorderBegin, leftInorderEnd, s2, leftPreorderBegin, leftPreorderEnd);root->right = traversal(s1, rightInorderBegin, rightInorderEnd, s2, rightPreorderBegin, rightPreorderEnd);return root;
}void dfs(node *root) {if (!root) return ;dfs(root->left);dfs(root->right);cout << root->val;
}int main() {node *tree;string s1, s2;cin >> s1 >> s2;tree = traversal(s1, 0, s1.size(), s2, 0, s2.size());dfs(tree);return 0;
}

在这里插入图片描述

四、优化

通过上面可以发现,他在生成树的过程中,就是经行的后续遍历。所以不用直接生成树。

#include <iostream>
using namespace std;void traversal(string s1, int inorderBegin, int inorderEnd, string s2, int preorderBegin, int preorderEnd) {if (preorderEnd == preorderBegin) return;char val = s2[preorderBegin];int delimiterIndex; // 左右子树的分割点for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {if (s1[delimiterIndex] == val) break;}// 左子树// 中序int leftInorderBegin = inorderBegin;int leftInorderEnd = delimiterIndex;// 前序int leftPreorderBegin = preorderBegin + 1;int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;// 右子树int rightInorderBegin = delimiterIndex + 1;int rightInorderEnd = inorderEnd;int rightPreorderBegin = preorderBegin + delimiterIndex - inorderBegin + 1;int rightPreorderEnd = preorderEnd;traversal(s1, leftInorderBegin, leftInorderEnd, s2, leftPreorderBegin, leftPreorderEnd);traversal(s1, rightInorderBegin, rightInorderEnd, s2, rightPreorderBegin, rightPreorderEnd);cout << val;
}int main() {string s1, s2;cin >> s1 >> s2;traversal(s1, 0, s1.size(), s2, 0, s2.size());return 0;
}

五、相关题目

  • LeetCode 105. 从前序与中序遍历序列构造二叉树
  • LeetCode 106. 从中序与后序遍历序列构造二叉树

六、最后

创作不易,留个赞,鼓励一下把!

相关文章:

P1827 [USACO3.4] 美国血统 American Heritage(前序 + 中序 生成后序)

P1827 [USACO3.4] 美国血统 American Heritage&#xff08;前序 中序 生成后序&#xff09; 一、前言 二叉树入门题。涉及到树的基本知识、树的结构、树的生成。 本文从会从结构&#xff0c;到完成到&#xff0c;优化。 二、基础知识 Ⅰ、二叉树的遍历 前序遍历&#xff…...

【四、centOS安装docker】

安装docker sudo yum install -y yum-utils device-mapper-persistent-data lvm2 如果以上报错 备份系统自带yum源配置文件 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup进入 /etc/yum.repos.d cd /etc/yum.repos.d删除文件 rm -f *.r…...

想学嵌入式开发,薪资怎么样?

想学嵌入式开发&#xff0c;薪资怎么样&#xff1f; 对于嵌入式工程师来说呢&#xff0c;它重点学习内容就是首先一定要打好基础&#xff0c;如果从编程语言角度来讲&#xff0c;那么可以在语言上选C或者C&#xff0c;你可以选择其中任何一门语言作为你的入门。 最近很多小伙伴…...

SQL死锁进程内容查询语句

1.方式1 SELECT object_name(A.resource_associated_entity_id) as TABLENAME, A.request_session_id AS SPID,DB_NAME(B.dbid) AS DBName,B.blocked,B.dbid,B.program_name,B.waitresource,B.lastwaittype,B.loginame,B.hostname,B.login_time,B.last_batch--,B.* FROM sy…...

Ubuntu 20.04中Nightingale二进制部署

参考博客《【夜莺监控】初识夜莺&#xff0c;强&#xff01;》 lsb_release -r可以看到操作系统版本是20.04&#xff0c;uname -r可以看到内核版本是5.5.19。 sudo apt-get update进行更新镜像源。 完成之后&#xff0c;如下图&#xff1a; sudo apt-get upgrade更新软件…...

深入探讨Java面试中内存泄漏:如何识别、预防和解决

引言 在编写和维护Java应用程序时&#xff0c;内存泄漏是一个重要的问题&#xff0c;可能导致性能下降和不稳定性。本文将介绍内存泄漏的概念&#xff0c;为什么它在Java应用程序中如此重要&#xff0c;并明确本文的目标&#xff0c;即识别、预防和解决内存泄漏问题。 内存泄…...

win10 安装.net framework 3.5,错误代码0x8024401C

win10 安装.net framework 3.5&#xff0c;错误代码0x8024401C 参考链接&#xff1a;https://www.gxlsystem.com/diannaowenti-386775.html 解决方法如下&#xff0c;cmd中执行&#xff1a; net stop wuauserv reg delete HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\W…...

杂记 | Langchain中few-shot提示词模板的使用(给提示词添加示例)

文章目录 01 普通的提示词模板02 few-shot提示词模板 Langchain是一个集成多个大语言模型的开源框架&#xff0c;可以使用它来快速开发大语言模型应用。 本文的代码使用到的模块&#xff1a; from typing import List, Dict from langchain import PromptTemplate, FewShotPr…...

SVN -基础

SVN - 基础 概念操作步骤开发实际经验 概念 带SVN路径 有隐藏文件&#xff0c;记录repo的一些信息&#xff0c;与repo进行关联&#xff0c;可以与repo进行同步 不带SVN路径 只是单纯的文件&#xff0c;与repo独立 操作步骤 checkout 具有路径 URLcheckout dir 输出目标文件夹…...

MySQL基础终端命令与Python简单操作MySQL

文章目录 MySQL终端命令1. 进入mysql2. 创建数据库3. 选择数据库4. 创建数据表1. 主键约束2. 外键约束3. 非空约束4. 唯一约束5. 使用默认约束6. 设置id为自增列 5. 查看数据表6. 修改数据表1. 修改表名2. 修改表的字段类型3. 修改表的字段名4. 为表添加字段5. 删除字段6. 调整…...

编译原理.龙书学习1

第一章&#xff1a; 编译器&#xff1a;将程序翻译成一种能够被计算机执行的形式 解释器&#xff1a;解释器直接利用用户提供的输入执行源程序中指定的操作 一个编译器的结构 编译器将源程序映射为语义上等价的目标程序&#xff0c;这个映射过程由两部分组成&#xff1a;分析…...

anaconda安装完成之后输入conda -V没有反应

anaconda安装完成后&#xff0c;conda没有反应 vim ~/.bashrc后面添加内容 # added by Anaconda3 5.3.0 installer # >>> conda init >>> # !! Contents within this block are managed by conda init !! __conda_setup"$(CONDA_REPORT_ERRORSfalse /u…...

netty报文解析之粘包半包问题

粘包问题 Netty 的粘包问题是指在网络传输过程中&#xff0c;由于 TCP 协议本身的特点&#xff0c;导致发送方发送的若干个小数据包被接收方合并成了一个大数据包。这种情况称为粘包。 TCP 协议是面向流的协议&#xff0c;没有数据边界&#xff0c;发送方发送的数据可能会被分…...

EasyCode整合mybatis-plus的配置

文章目录 entitymapper.javamapper.xmlserviceserviceImplcontroller 这篇文章不教你如何安装和使用EasyCode&#xff0c;只是贴出可以使用的配置。 具体EasyCode的使用可以查看其它的文章。 entity ##导入宏定义 $!{define.vm}##保存文件&#xff08;宏定义&#xff09; #sa…...

实施预测性维护解决方案的挑战及PreMaint的应对方法

前面我们介绍了企业选择预测性维护解决方案的常见问题和PreMaint的策略&#xff0c;本期我们将带来实施过程中可能会遇到的挑战&#xff0c;以及如何通过PreMaint来应对这些挑战&#xff0c;以实现可靠的预测性维护。 随着工业技术的不断进步&#xff0c;预测性维护作为一种先进…...

1. js中let、var、const定义变量区别与方式

1 声明语法 var upperA A; let upperB B; const upperC C; 只声明不初始化的结果&#xff0c;【 const定义的常量不可以修改&#xff0c;而且必须初始化】 // var 声明变量 var upperA; console.log(打印大写的A&#xff1a;%s, upperA); // 结果&#xff1a;打印大写的A&am…...

【STM32学习】I2C通信协议 | OLED屏

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《STM32学习》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 今天需要将代码烧录到开发板中&#xff0c;本喵默认大家都会创建工程&#xff0c;以及进行基本的…...

Nvme Spec 第一章节学习

Nvme Express Base Specification 第一章 简介 1.1概述 NVM ExpressTM&#xff08;NVMeTM&#xff09;接口允许主机软件与非易失性存储器子系统通信。 此接口针对企业和客户端固态驱动器进行了优化&#xff0c;通常作为寄存器级接口连接到PCI Express接口。 注&#xff1a;在…...

第一章:最新版零基础学习 PYTHON 教程(第九节 - Python 语句中的 – 多行语句)

Python 中的语句: 在Python中,语句是Python解释器可以读取和执行的逻辑命令。它可能是Python 中的赋值语句或表达式。 Python 中的多行语句: 在Python中,语句通常写成一行,每行的最后一个字符是换行符。要将语句扩展到一行或多行,我们可以使用大括号 {}、圆括号 ()、方…...

kafka 3.0 离线安装

1.安装zookeeper 解压apache-zookeeper-3.8.0-bin.tar.gz到指定目录,复制conf目录下zoo_sample.cfg到zoo.cfg,并修改配置。 # The number of milliseconds of each tick tickTime=2000 # The number of ticks that the initial # synchronization phase can take initLimit…...

MySQL数据库入门到精通2--基础篇(函数,约束,多表查询,事务)

3. 函数 函数 是指一段可以直接被另一段程序调用的程序或代码。MySQL中的函数主要分为以下四类&#xff1a; 字符串函数、数值函数、日期函数、流程函数。 3.1 字符串函数 MySQL中内置了很多字符串函数&#xff0c;常用的几个如下&#xff1a; 演示如下&#xff1a; A. con…...

c-数据在内存中的存储-day7

...

3D大模型如何轻量化?试试HOOPS Communicator,轻松读取10G超大模型!

随着计算机技术的不断发展&#xff0c;3D模型在各行各业中的应用越来越广泛。然而&#xff0c;随着模型的复杂性和规模不断增加&#xff0c;处理和浏览超大型3D模型变得越来越具有挑战性。本文将探讨如何轻量化3D大模型&#xff0c;以及如何使用HOOPS Communicator来读取和浏览…...

go并发操作且限制数量

使用管道chan func returnNum() int64 {return time.Now().Unix() } func main() {threadAmount : runtime.GOMAXPROCS(0)if threadAmount < 2 {threadAmount 2}fmt.Println(threadAmount)threadChan : make(chan int, threadAmount)defer close(threadChan)for {for i :…...

AI深度学习-卷积神经网络000

文章目录 前言1.什么是深度学习2.语义分割与实例分割概述3.什么是卷积&#xff1f;4.Unet网络 前言 本栏目&#xff0c;主要为深度学习保姆教程。 主要通过B站视频整理而来&#xff1a; 深度学习保姆级教学 Unet语义分割视觉三维重建算法 1.什么是深度学习 深度学习保姆级教…...

网站有反爬机制就爬不了数据?那是你不会【反】反爬

目录 前言 一、什么是代理IP 二、使用代理IP反反爬 1.获取代理IP 2.设置代理IP 3.验证代理IP 4.设置代理池 5.定时更新代理IP 三、反反爬案例 1.分析目标网站 2.爬取目标网站 四、总结 前言 爬虫技术的不断发展&#xff0c;使得许多网站都采取了反爬机制&#xff…...

2023华为杯研究生数学建模C题分析

完整的分析查看文末名片获取&#xff01; 问题一 在每个评审阶段&#xff0c;作品通常都是随机分发的&#xff0c;每份作品需要多位评委独立评审。为了增加不同评审专家所给成绩之间的可比性&#xff0c;不同专家评审的作品集合之间应有一些交集。但有的交集大了&#xff0c;则…...

第三天:实现网络编程基于tcp/udp协议在Ubuntu与gec6818开发板之间双向通信

互联网地址 每一台设备接入互联网后&#xff0c;都会举报一个唯一的地址编号 IP地址 INTERNET地址 internet地址 &#xff1a;它是协议上的一个逻辑地址 目前来说&#xff0c;我们主要的IP地址有两类 IPV4 IPV6 IPV4 其实就是使用一个32bit整数作为IP IPV6 其实就是使用一…...

【MediaSoup---源码篇】(三)Transport

概述 RTC::Transport是mediasoup中的一个重要概念&#xff0c;它用于在mediasoup与客户端之间传输实时音视频数据。 Transport继承着众多的类&#xff0c;主要用于Transport的整体感知 class Transport : public RTC::Producer::Listener,public RTC::Consumer::Listener,publ…...

爱分析《商业智能最佳实践案例》

近日&#xff0c;国内知名数字化市场研究咨询机构爱分析发布《2023爱分析商业智能最佳实践案例》&#xff0c;此评选活动面向落地商业智能的各行企业和商业智能厂商&#xff0c;以第三方专业视角深入调研&#xff0c;评选出具有参考价值的创新案例。永达汽车集团与数聚股份合作…...

注册域名网站/软文推广发稿平台

开发工具准备&#xff1a; 1&#xff0e;apache-cxf-2.2.6.zip 2&#xff0e;spring-ws-1.5.8.zip 3&#xff0e;eclipse-jee-galileo-SR1-win32 开发步骤&#xff1a; 一、新建一个普通的java工程&#xff0c;名字叫WebService_CXF_Client 二、导入apache-cxf-2.2.6 及 spring…...

网站开发项目管理/seo网站优化案例

top&#xff1a;动态查看进程的变化 ps:将某个时间点的进程运行情况选取下来 ps -l :仅查看自己的bash相关进程 ps -aux :查看系统所有的进程 pstree :列出目前系统上面所有的进程树的相关性 netstat 转载于:https://www.cnblogs.com/MUMO/p/8279156.html...

周口 网站建设/网站建设山东聚搜网络

ElasticSearch入门、ES概念介绍和安装 一.ElasticSearch相关概念 1.1.ElasticSearch介绍 1.1.1.什么是ES ​ ES是一个分布式的全文搜索引擎&#xff0c;为了解决原生Lucene使用的不足&#xff0c;优化Lucene的调用方式&#xff0c;并实现了高可用的分布式集群的搜索方案&am…...

长春建站方案/营销战略包括哪些方面

LVM配置及磁盘配额LVM基本概念LVM构成LVM命令LVM配置磁盘配额磁盘配额配置LVM基本概念 LVM (Logical Volume Manager)&#xff0c;逻辑卷管理 在保持现有数据不变的情况下动态的调整磁盘容量&#xff0c;提高磁盘管理的灵活性 注&#xff1a;/boot分区用于存放引导文件&…...

东营做网站的公司/国际羽联最新排名

本节主要总结以下几个内容&#xff1a; 对model泛化能力进行评估的实验方法model性能的度量指标用统计检验的方法 比较不同model之间性能的差异解析 model 的 bias and variance 一、对model泛化能力进行评估的实验方法 当我们训练好一个模型时&#xff0c;往往希望知道的并…...

网站建设案例平台/手机关键词点击排名软件

在当今高度自动化、技术驱动的经济环境下&#xff0c;业务能力与IT能力正越发密不可分。IT已经成为企业推动自身业务向前发展的重要赋能器&#xff0c;IT基础架构从根本上决定了业务的成败。然而&#xff0c;由于 IT基础架构日益复杂&#xff0c;不灵活、脆弱和昂贵正成为其代名…...