【二叉树】hdu 1710 Binary Tree Traversals
2024-09-04 15:30:51
acm.hdu.edu.cn/showproblem.php?pid=1710
【题意】
给定一棵二叉树的前序遍历和中序遍历,输出后序遍历
【思路】
根据前序遍历和中序遍历递归建树,再后续遍历输出
malloc申请空间在堆,函数返回,内存不释放,需要free手动释放
【Accepted】
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm> using namespace std;
const int maxn=1e3+;
int n;
int pre[maxn],in[maxn],post[maxn];
int mp[maxn];
struct node{
int id;
node *lef;
node *rig;
node(int i, node *l=NULL, node *r=NULL):id(i),lef(l),rig(r){}
};
node* dfs(int l,int r,int x,int y){
if(l>r) return NULL;
node *nd=(node *)malloc(sizeof(node));
nd->id=in[y];
nd->lef=dfs(l,y-,x+,mp[pre[x+]]);
nd->rig=dfs(y+,r,x+y-l+,mp[pre[x+y-l+]]);
return nd;
}
void postorder(node *root){
if(root==NULL) return;
postorder(root->lef);
postorder(root->rig);
if(root->id==pre[]){
printf("%d\n",root->id);
}else{
printf("%d ",root->id);
}
free(root);
}
int main(){
while(~scanf("%d",&n)){
for(int i=;i<n;i++){
scanf("%d",&pre[i]);
}
for(int i=;i<n;i++){
scanf("%d",&in[i]);
mp[in[i]]=i;
}
if(n==) {
printf("1\n");
continue;
}
node *root=dfs(,n-,,mp[pre[]]);
postorder(root);
}
return ;
}
最新文章
- NC凭证接口(Java发送流和处理返回结果)
- ACM: SCU 4440 Rectangle - 暴力
- SQL查询语句中的 limit offset(转 )
- (WPF, Service) 删除注册表中的USB Enum值.
- 一段实现页面上的图片延时加载的js
- 玩转SmartQQ之登录
- 求职基础复习之快速排序c++版
- iBeacon
- cloudstack安装篇2-主机名配置
- ASP.NET MVC- VIEW Creating Page Layouts with View Master Pages Part 4
- Swift &; OC 混编 浅析
- 制作windows镜像
- zookeeper启动失败
- 【转载】CANoe 入门 Step by step系列(三)简单例子的剖析
- 网络模型 - 每天5分钟玩转 Docker 容器技术(169)
- SpringBoot中的ajax跨域问题
- Latex自定义文档纸张大小
- mabatis的批量新增sql 初级的 初级的 初级的
- Android 音视频深入 四 录视频MP4(附源码下载)
- 通过经纬度坐标计算距离的方法(经纬度距离计算)ZZ
热门文章
- 初习mysql procedure
- ARC和MRC混合模式下的编译问题
- 在Solr中配置中文分词IKAnalyzer
- com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failure
- Codeforces Round #271 (Div. 2)-B. Worms
- 【Codeforces #228】Solutions
- css--float浮动
- react native在xcode真机调试ios
- java常考小程序
- CentOS7支持中文显示