03-树3 Tree Traversals Again(浙大数据结构PTA习题)
03-树3 Tree Traversals Again 分数 25 作者 陈越
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.
Figure 1
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop
Sample Output:
3 4 2 6 5 1
代码长度限制:16 KB 时间限制:400 ms 内存限制:64 MB
题目解析:
本质是根据一棵树的先序遍历结果和中序遍历结果,求解这棵树的后序遍历结果。
在树的遍历中,知中序和先序可求唯一后序;知中序和后序可求唯一先序;知先序和后序不可求唯一中序。
关键点1:根据输入获得先序遍历结果和中序遍历结果
关键点2:根据先序和中序遍历结果输出后序遍历结果
下面将演示建树和不建树两种情况
代码展示:
不建树的情况
// 根据先序遍历与中序遍历求后序遍历# include<stdio.h>
# include<string.h>
# define MAXSIZE 5void Solve(int preL, int inL, int postL, int n, int pre[], int in[], int post[]);int main(){// 一共有多少个结点 int N;scanf("%d",&N);// 创建一个堆栈int Stack[N];int Rear = -1;// 分别创建前、中、后序遍历的结果数组int Pre[N],In[N],Post[N];int PreRear = -1;// count作为弹出元素的计数int num, count = 0;while(count!=N){char handle[MAXSIZE];scanf("%s",handle);if(!strcmp(handle,"Push")){// 接受一个数字并压入栈scanf("%d",&num);Stack[++Rear] = num; // 前序遍历数组记录Pre[++PreRear] = num; }else{// 出栈并在中序遍历中进行记录 num = Stack[Rear--];In[count++] = num;}} // 有了前序与中序遍历结果,接下来通过递归函数求后序遍历结果 Solve(0,0,0,N,Pre,In,Post);int i;for(i=0;i<N;i++){if(i!=N-1)printf("%d ",Post[i]);else printf("%d",Post[i]);}
} void Solve(int preL, int inL, int postL, int n, int pre[], int in[], int post[]){if(n==0)return;if(n==1){post[postL] = pre[preL];return;}// 先序的第一个放在给定后序的最后一个 int root = pre[preL];post[postL+n-1] = root;// 找出左子树的范围 int i;for(i=0;i<n;i++){if(in[inL+i]==root)break;}// 左子树要处理的的结点数 int L = i;// 右子树要处理的结点数 int R = n-L-1;// 递归处理 Solve(preL+1, inL, postL,L,pre,in,post);Solve(preL+L+1,inL+L+1,postL+L,R,pre,in,post);return;
}
建树的情况:
# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# define MAXNODE 30
# define MAXLENGTH 5typedef struct TreeNode* Tree;
struct TreeNode{int data;Tree left;Tree right;
}; void PostOrder(Tree root,int data);
void CreateTree(int left1,int right1,int left2,int right2,int Pre[],int In[], Tree root);int main(){// 创建一个堆栈int Stack[MAXNODE];int SHead = -1; // 接收结点个数 int N;scanf("%d",&N);getchar();// 分别创建一个用来记录先序和中序遍历结果的数组int PreArray[N],InArray[N];int PreHead=-1, InHead=-1;// 接收操作输入,因为有出入栈,因此共有2*N次操作 int i,num;char* str = (char*)malloc(sizeof(char)*MAXLENGTH);for(i=0;i<2*N;i++){scanf("%s",str);if(strcmp(str,"Push")==0){// 入栈scanf("%d",&num);getchar();Stack[++SHead] = num;// 记录先序PreArray[++PreHead] = num; }else{// 出栈num = Stack[SHead--];// 记录中序InArray[++InHead] = num; }}// 创建根结点Tree root = (Tree)malloc(sizeof(struct TreeNode));root->data = PreArray[0];root->left = NULL;root->right = NULL;// 构建树CreateTree(0,N-1,0,N-1,PreArray,InArray,root);// 后序输出遍历结果,为了格式化输出因此传入根结点的值作为判读依据 PostOrder(root,root->data); return 0;
}// 递归后序遍历树
void PostOrder(Tree root,int data){if(root){PostOrder(root->left,data);PostOrder(root->right,data);if(root->data == data)printf("%d",root->data);else printf("%d ",root->data);}return;
} // 根据先序和后序构建一棵树;left1与right1表示先序序列的范围;left2与right2表示后序序列的范围
void CreateTree(int left1,int right1,int left2,int right2,int Pre[],int In[], Tree root){// 首先找到根结点在中序中的位置int i,index;for(i=left2;i<=right2;i++){if(root->data == In[i]){index = i;break;}} // 如果根结点有左孩子 if(index!=left2){// 创建一个左孩子结点Tree left_son = (Tree)malloc(sizeof(struct TreeNode));left_son->data = Pre[left1+1];left_son->left = NULL;left_son->right = NULL;root->left = left_son;// 递归构建这个左孩子结点CreateTree(left1+1,index-left2+left1,left2,index-1,Pre,In,left_son); }// 如果根结点有右孩子if(index!=right2){Tree right_son = (Tree)malloc(sizeof(struct TreeNode));right_son->data = Pre[index-left2+left1+1];right_son->left = NULL;right_son->right = NULL;root->right = right_son;// 递归构建这个右孩子结点CreateTree(index-left2+left1+1,right1,index+1,right2,Pre,In,right_son); } return;
}
运行结果:
两种情况均可通过测试点
相关文章:

03-树3 Tree Traversals Again(浙大数据结构PTA习题)
03-树3 Tree Traversals Again 分数 25 作者 陈越 An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, th…...

Java项目对接redis,客户端是选Redisson、Lettuce还是Jedis?
JAVA项目对接redis,客户端是选Redisson、Lettuce还是Jedis? 一、客户端简介1. Jedis介绍2. Lettuce介绍3. Redisson介绍 二、横向对比三、选型说明 在实际的项目开发中,对于一个需要对接Redis的项目来说,就面临着选择合适的Redis客…...
AngularJS Web前端框架:深入探索与应用实践
AngularJS Web前端框架:深入探索与应用实践 AngularJS,作为一款强大的Web前端框架,为开发者提供了丰富的功能和工具,使得构建复杂且交互性强的Web应用变得更为便捷。本文将从四个方面、五个方面、六个方面和七个方面对AngularJS进…...
SQL 入门:使用 MySQL 进行数据库操作
SQL 入门:使用 MySQL 进行数据库操作 目录 引言SQL 基础 SQL 语言概述MySQL 简介 数据库设计基础 数据库与表的设计常见数据类型 MySQL 安装与配置 安装 MySQL基本配置与连接 基本 SQL 语句 数据库的创建与删除表的创建、修改与删除数据插入、更新与删除 数据查询…...

window安装ffmpeg播放本地摄像头视频
1、安装ffmpeg ffmpeg官方网站:FFmpeg 下载后解压文件夹名为ffmpeg 2、设置环境变量 目录 1、安装ffmpeg 设置环境变量 以F:\software\after\ffmpeg\bin为例 在命令行中输入ffmpeg出现下方代表安装成功 3、通过ffmpeg播放本地电脑摄像头 鼠标右击开始按钮&…...

【嵌入式DIY实例】-OLED显示网络时钟
OLED显示网络时钟 文章目录 OLED显示网络时钟1、硬件准备与接线2、代码实现在上一个ESP8266 NodeMCU文章中,我们用DS3231 RTC芯片和SSD1306 OLED制作了一个简单的实时时钟,时间和日期显示在SSD1306屏幕上,并且可以通过两个按钮进行设置。 在本中,我们将使用ESP 8266 NodeMC…...
【线程相关知识】
今日内容概要 开启线程的两种方式TCP服务端实现并发效果线程对象的join方法线程间数据共享线程对象属性及其他方法守护线程线程互斥锁GIL全局解释器锁多进程与多线程的实际应用场景 今日内容详细 开启线程的两种方式 # import time # from multiprocessing import Process #…...

鸿蒙ArkTS声明式开发:跨平台支持列表【透明度设置】 通用属性
透明度设置 设置组件的透明度。 说明: 开发前请熟悉鸿蒙开发指导文档: gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md点击或者复制转到。 从API Version 7开始支持。后续版本如有新增内容,则采用上角标单独标记该内容的起始版…...

【SQL学习进阶】从入门到高级应用(九)
文章目录 子查询什么是子查询where后面使用子查询from后面使用子查询select后面使用子查询exists、not existsin和exists区别 union&union alllimit 🌈你好呀!我是 山顶风景独好 💕欢迎来到我的博客,很高兴能够在这里和您见面…...
Web前端三大主流框架技术分享
在当今快速发展的互联网时代,Web前端技术作为连接用户与服务的桥梁,其重要性不言而喻。随着技术的不断进步,为了提升开发效率、优化用户体验,一系列强大的前端框架应运而生。其中,Angular、React和Vue.js作为当前最为主…...

dockers安装mysql
1.dockerhub上搜索自己需要安装得镜像版本 dockerhub网址:https://hub-stage.docker.com docker pull mysql:5.7 #下载自己需要得版本2.启动容器实例,并且挂载容器数据卷 docker run -d -p 3306:3306 --privilegedtrue \ -v /home/mysql/log:/var/log/…...

100道面试必会算法-27-美团2024面试第一题-前缀和矩阵
100道面试必会算法-27-美团2024面试第一题-前缀和矩阵 问题解读 给定一个 n x n 的二进制矩阵,每个元素是 0 或 1。我们的任务是计算矩阵中所有边长为 k 的子矩阵中,包含特定数量 1 的情况。例如,我们希望找到所有边长为 k 的子矩阵中包含 k…...

从摇一摇到弹窗,AD无处不在?为了不再受打扰,推荐几款好用的屏蔽软件,让手机电脑更清爽
当我们沉浸在智能手机带来的便捷与乐趣中时,内置AD如同不速之客,时常打断我们的体验。 尤其是手机上那些“摇一摇”跳转,稍有不慎就会跳转到其他应用,令人不胜其烦。同样,电脑上的内置AD也如影随形,影响了我…...

HackTheBox-Machines--Nibbles
Nibbles 测试过程 1 信息收集 NMAP 80 端口 网站出了打印出“Hello world!”外,无其他可利用信息,但是查看网页源代码时,发现存在一个 /nibbleblog 文件夹 检查了 http://10.129.140.63/nibbleblog/ ,发现了 /index.p…...
东方博宜1703 - 小明买水果
问题描述 小明去超市买了若干斤水果,你能根据水果的单价,小明买的水果数量,编一个程序计算出总金额,并打印出清单。 输入 输入两个值, 第一个为商品的单价,是一个小数。 第二个为商品的数量,…...

mac电脑用谷歌浏览器对安卓手机H5页面进行inspect
1、mac上在谷歌浏览器上输入 chrome://inspect 并打开该页面。 2、连接安卓手机到Mac电脑:使用USB数据线将安卓手机连接到Mac电脑。 3、手机上打开要的h5页面 Webview下面选择要的页面,点击inspect,就能像谷歌浏览器页面打开下面的页面&#…...
动手学深度学习(Pytorch版)代码实践-深度学习基础-01基础函数的使用
01基础函数的使用 主要内容 张量操作:创建和操作张量,包括重塑、填充、逐元素操作等。数据处理:使用pandas加载和处理数据,包括处理缺失值和进行one-hot编码。线性代数:包括矩阵运算、求和、均值、点积和各种范数计算…...

vm-bhyve:bhyve虚拟机的管理系统@FreeBSD
先说情况,当前创建虚拟机后网络没有调通....不明白是最近自己点背,还是确实有难度... 缘起: 前段时间学习bhyve虚拟机,发现bvm这个虚拟机管理系统,但是实践下来发现网络方面好像有问题,至少我花了两天时间…...

【Java】刚刚!突然!紧急通知!垃圾回收!
【Java】刚刚!突然!紧急通知!垃圾回收! 文章目录 【Java】刚刚!突然!紧急通知!垃圾回收!从C语言的内存管理引入:手动回收Java的垃圾回收机制引用计数器循环引用问题 可达…...

[Algorithm][动态规划][子序列问题][最长递增子序列][摆动序列]详细讲解
目录 0.子序列 vs 子数组1.最长递增子序列1.题目链接2.算法原理详解3.代码实现 2.摆动序列1.题目链接2.题目链接3.代码实现 0.子序列 vs 子数组 子序列: 相对顺序是跟源字符串/数组是一致的但是元素和元素之间,在源字符串/数组中可以是不连续的一般时间…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...

Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
Linux中INADDR_ANY详解
在Linux网络编程中,INADDR_ANY 是一个特殊的IPv4地址常量(定义在 <netinet/in.h> 头文件中),用于表示绑定到所有可用网络接口的地址。它是服务器程序中的常见用法,允许套接字监听所有本地IP地址上的连接请求。 关…...

生信服务器 | 做生信为什么推荐使用Linux服务器?
原文链接:生信服务器 | 做生信为什么推荐使用Linux服务器? 一、 做生信为什么推荐使用服务器? 大家好,我是小杜。在做生信分析的同学,或是将接触学习生信分析的同学,<font style"color:rgb(53, 1…...