树的重构【东北大学oj数据结构7-4】C++

news/2024/12/12 14:53:54/
题面

编写一个程序,分别读取二叉树上前序树遍历和中序树遍历得到的两个节点序列,并在二叉树上打印后序树遍历得到的节点序列。

输入

第一行给出了一个整数 n,它是二叉树中的节点数。(1≤n≤40)
在第二行中,通过前序树遍历获得的节点 ID 序列以空格字符分隔给出。
在第二行中,通过中序树遍历获得的节点 ID 序列以空格字符分隔给出。

每个节点都有一个从 1 到 n 的唯一 ID。 请注意,根并不总是对应于 1。

输出

将后序树遍历获得的节点 ID 序列打印成一行。 在相邻 ID 之间放置一个空格字符。

输入样例

5
1 2 3 4 5
3 2 4 1 5

输出样例

3 4 2 5 1

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
using namespace std;#define MAX 41// 定义树的节点结构
struct Node {int p, l, r;
};struct Node T[MAX];  // 树节点数组
int n;  // 节点的数量
unordered_map<int,int> m;int buildtree(int po[],int ps,int pe,int io[],int is,int ie)
{if(ps>pe||is>ie)return -1;int rootval=po[ps];int rootidx=m[rootval];int leftsize=rootidx-is;T[rootval].p=-1;T[rootval].l=buildtree(po,ps+1,ps+leftsize,io,is,rootidx-1);T[rootval].r=buildtree(po,ps+leftsize+1,pe,io,rootidx+1,ie);if(T[rootval].l!=-1)T[T[rootval].l].p=rootval;if(T[rootval].r!=-1)T[T[rootval].r].p=rootval;return rootval;
}void posorder(int root)
{if(root==-1) return;stack<int> s1,s2;s1.push(root);while(!s1.empty()){int node=s1.top();s1.pop();s2.push(node);if(T[node].l!=-1)s1.push(T[node].l);if(T[node].r!=-1)s1.push(T[node].r);}while(!s2.empty()){cout<<s2.top()<<" ";s2.pop();}
}int main() {int v;int a[41],b[41];scanf("%d", &n);for (int i = 0; i < n; i++) {T[i].p = T[i].l = T[i].r = -1;}for (int i = 0; i < n; i++) {scanf("%d", &v);a[i]=v;}for (int i = 0; i < n; i++) {scanf("%d", &v);b[i]=v;m[v]=i;}int root=buildtree(a,0,n-1,b,0,n-1);posorder(root);return 0;
}

 


http://www.ppmy.cn/news/1554525.html

相关文章

频域滤波中默认的边界条件——补零与不补零(答作者问)

这个问题源自于Rafael Gonzalez的《数字图像处理》中的这幅图&#xff0c;为什么他频域滤波要将图像零延拓到二倍尺寸&#xff1f; 完全没有没要&#xff0c;既浪费计算&#xff0c;又浪费空间。 廖老师的问题是图像滤波涉及到源图像和滤波器相卷&#xff0c;卷积结果尺寸要大…

5分钟入门SpringAi - java快速接入国内大模型

本文的协作目的是帮你怎样用Spring AI给Java项目加上通义千问的AI功能。 会从设置环境讲到写代码的具体步骤。 例子使用的是spring ai alibaba和QWen千问API。你可以先试着跑通例子&#xff0c;再换成自己的实现。 现在QWen有100万免费Token可以用&#xff0c;很适合快速开发…

Spring Boot 集成阿里云OSS 完成文件上传下载

前言&#xff1a; 文件上传下载在项目开发中是一个非常常见的业务场景&#xff0c;在云服务上还没有兴起的时候&#xff0c;一般来说都会把文件单独存放到文件服务器上&#xff0c;随着云服务的兴起&#xff0c;各类云服务厂商都提供了 OSS 服务&#xff0c;本篇我们分享 Spri…

嵌入式蓝桥杯学习6 定时中断按键(短按 长按 双击)

前面的cubemx配置都和定时中断的一样&#xff0c;详情请看上文&#xff0c;这篇我们主要写按键相关的代码。 前面的外部中断的按键&#xff0c;还有直接写的按键函数都不适用于比赛&#xff0c;各有不同缺点。在比赛中按键又是个很重要的外设&#xff0c;那如何实现按键呢&…

【Android】车芯 | 使用HTP运行设备端模型

首先,确保运行在设备的模型制作过程以及host端验证已完成啦。模型制作过程可参考:【qualcomm】QNN SDK的下载以及运行在设备端的模型制作-CSDN博客 本文以之前生成的Resnet18_quantized.bin作为测试模型。 1 新建文件夹/data/test

Socks5机房代理IP的测试与挑选指南

选择合适的代理IP不仅能够提升您的网络体验&#xff0c;还能够保护您的个人信息和数据安全&#xff0c;让您更加安心地畅游互联网世界。因此如何测试和挑选合适的代理IP就显得尤为重要。本文将为您详细介绍测试和挑选方法。 1. 确定测试指标 在测试和挑选之前&#xff0c;首先…

单片机:实现贪吃蛇(附带源码)

单片机实现贪吃蛇游戏是一个较为复杂的项目&#xff0c;涉及到硬件控制、程序设计、图形显示、输入处理等方面。这里我们以基于8051单片机为例&#xff0c;详细介绍如何通过硬件和软件来实现一个简单的贪吃蛇游戏。为了让解释更加清晰&#xff0c;我们将逐步分析贪吃蛇的游戏逻…

RPO: Read-only Prompt Optimization for Vision-Language Few-shot Learning

文章汇总 想解决的问题 对CoOp的改进CoCoOp尽管提升了性能&#xff0c;但却增加了方差&#xff08;模型的准确率波动性较大&#xff09;。 模型的框架 一眼看去&#xff0c;跟maple很像(maple跟这篇文章都是2023年发表的)&#xff0c;但maple的视觉提示是由文本提示经过全连接…