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 ;
}

最新文章

  1. NC凭证接口(Java发送流和处理返回结果)
  2. ACM: SCU 4440 Rectangle - 暴力
  3. SQL查询语句中的 limit offset(转 )
  4. (WPF, Service) 删除注册表中的USB Enum值.
  5. 一段实现页面上的图片延时加载的js
  6. 玩转SmartQQ之登录
  7. 求职基础复习之快速排序c++版
  8. iBeacon
  9. cloudstack安装篇2-主机名配置
  10. ASP.NET MVC- VIEW Creating Page Layouts with View Master Pages Part 4
  11. Swift &amp; OC 混编 浅析
  12. 制作windows镜像
  13. zookeeper启动失败
  14. 【转载】CANoe 入门 Step by step系列(三)简单例子的剖析
  15. 网络模型 - 每天5分钟玩转 Docker 容器技术(169)
  16. SpringBoot中的ajax跨域问题
  17. Latex自定义文档纸张大小
  18. mabatis的批量新增sql 初级的 初级的 初级的
  19. Android 音视频深入 四 录视频MP4(附源码下载)
  20. 通过经纬度坐标计算距离的方法(经纬度距离计算)ZZ

热门文章

  1. 初习mysql procedure
  2. ARC和MRC混合模式下的编译问题
  3. 在Solr中配置中文分词IKAnalyzer
  4. com.mysql.jdbc.exceptions.jdbc4.CommunicationsException: Communications link failure
  5. Codeforces Round #271 (Div. 2)-B. Worms
  6. 【Codeforces #228】Solutions
  7. css--float浮动
  8. react native在xcode真机调试ios
  9. java常考小程序
  10. CentOS7支持中文显示