PAT甲级1020 Tree Traversals:[C++题解]树的遍历、由中序序列和后序序列递归建树

本文主要是介绍PAT甲级1020 Tree Traversals:[C++题解]树的遍历、由中序序列和后序序列递归建树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 题目分析
    • 题目链接

题目分析

在这里插入图片描述
题意重述:给定一棵二叉树的后序遍历序列和中序遍历序列,让求层次遍历的序列。

分析:

后序遍历:先 左子树、右子树 ,最后再遍历根结点。

中序遍历:先左子树,再根结点,然后是右子树。

给定中序序列和后续序列,便可以唯一确定这棵二叉树的形状。

由于后序遍历最后遍历根结点,所以最后一个就是根结点。 找到根结点的值,我们就可以在中序序列中找到根结点,从而把中序序列分成左子树、根结点、右子树三部分。 这三部分也可以在后序序列中找到对应的部分。

然后对于后序序列的各个部分,递归上面这个过程,先找到这个部分的根结点,再对应到中序序列,把中序序列的这一部分再分成左子树、根结点、右子树三部分……

这里需要用到hash表l和r,分别用来存一个结点的左儿子 和右儿子。这样查找某结点是否存在儿子,就方便很多。
ac代码

#include<bits/stdc++.h>
using namespace std;const int N =40;int n;
int postOrder[N], inOrder[N];unordered_map<int,int> l,r,pos; //l和r存左右儿子,pos存中序遍历每个值的下标
int q[N];/*build函数:根据中序序列和后序序列建树,返回树根il:中序序列左端点;ir:中序序列右端点pl:后序序列左端点;pr:后序序列右端点
*/
int  build(int il, int ir, int pl ,int pr){int root = postOrder[pr];  //在后序序列中找到根结点的值,存在root中int k =pos[root];// 根结点在中序序列中的位置//看中序序列//中序序列中存在左子树if(il < k){//左子树的树根 就是 root的左儿子l[root] = build(il,k-1, pl,pl+(k-1-il));}//中序序列中存在右子树if(k<ir){//右子树的树根就是root的右儿子r[root] = build(k+1,ir,pl+(k-1-il)+1,pr-1);}return root; //返回树根
}
/*
bfs:层次遍历
手写队列*/
void bfs(int root){int hh =0 ,tt =0;q[0] =root;  //q[0]为根结点while(hh<=tt){ //队列不空int t =q[hh++]; //取队首元素//左子树存在,左子树的树根加入队列if(l.count(t)) q[++tt] =l[t];  //左儿子存在加入队列//右子树存在,右子树的树根加入队列if(r.count(t)) q[++tt] =r[t]; //右儿子存在加入队列}cout<<q[0];for(int i=1;i<n;i++) cout<<" "<<q[i];
}int main(){cin>> n;for(int i=0; i<n;i++) cin>> postOrder[i];for(int i=0;i<n;i++){cin>>inOrder[i];pos[inOrder[i]] =i; //记录每个值在中序序列中的位置}int root = build(0,n-1,0,n-1);bfs(root);}

题目链接

PAT甲级1020 Tree Traversals

这篇关于PAT甲级1020 Tree Traversals:[C++题解]树的遍历、由中序序列和后序序列递归建树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/465835

相关文章

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能(如数据库连接、事务管理)、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite:C++轻松操作SQ

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现:TCMalloc与Jemalloc1. TCM

基于Python实现一个Windows Tree命令工具

《基于Python实现一个WindowsTree命令工具》今天想要在Windows平台的CMD命令终端窗口中使用像Linux下的tree命令,打印一下目录结构层级树,然而还真有tree命令,但是发现... 目录引言实现代码使用说明可用选项示例用法功能特点添加到环境变量方法一:创建批处理文件并添加到PATH1

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》:本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》:本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数:不用传参就可以