以前就思考过这个问题,但是没有深入的想过,这是一种叫二叉树重建的典型题目

如果给出中序和前序,求出后序遍历。

这道题则求的是交换儿子节点的层序遍历。

二叉树的重建应该怎么重建,首先我们知道,先根遍历,最开始的那个一定是根节点,那么,我们可以从先根遍历开始,对于先根遍历的某个节点,寻找他在中根遍历中的位置,这个位置到先根遍历的位置,中间的节点一定是其左儿子节点,而中间节点后面,一定是右儿子节点。、

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<queue>
using namespace std;
const int maxx = ;
int pre[maxx];
int in[maxx];
int pos;
struct node{
int w,l,r;
}tree[maxx];
void build(int l,int r,int n)
{
if (l==r){
tree[n].w=-;//当前节点为空
return;
}
int root=pre[pos++];
tree[n].w=root;//当前节点存储的值
tree[n].l=*n;//这个节点的左儿子节点编号
tree[n].r=*n+;//这个节点的右儿子节点编号
int mid=find(in+,in+r,root)-in;// 得到当前节点在中序遍历数组中的下标
build(l,mid,*n);//重建左子树
build(mid+,r,*n+);//重建右子树
}
void print(){
queue<int>q;
q.push();
int s;
while(!q.empty()){
s=q.front();
q.pop();
if (tree[s].w!=-){
if (s!=){
printf(" ");
}
printf("%d",tree[s].w);
q.push(tree[s].r);
q.push(tree[s].l);
}
}
printf("\n");
}
int main(){
int n;
while(~scanf("%d",&n)){
pos=;
for (int i=;i<=n;i++){
scanf("%d",&in[i]);
}
for (int i=;i<=n;i++){
scanf("%d",&pre[i]);
}
build(,n+,);
print();
}
return ;
}

最新文章

  1. 初探微信小程序
  2. PHP错误处理函数set_error_handler()的用法
  3. JDK&amp;JRE&amp;JVM
  4. ef 对象无法序列化的问题(System.Data.Entity.DynamicProxies)
  5. Linux内核设计第四周——扒开系统调用三层皮
  6. 转--Android学习笔记-实用代码合集
  7. python 利用imap接收邮件,并保存附件
  8. Sereja and Suffixes(思维)
  9. VS解决BEX错误但不能关闭DEP保存
  10. nio简介
  11. C++ 头文件系列(system_error)
  12. Echarts数据可视化series-pie饼图,开发全解+完美注释
  13. Day4:html和css
  14. 转://使用insert插入大量数据的总结
  15. Python字符串和列表的内置方法
  16. js版的in_array的实现方法
  17. 华为交换机SNMP OID
  18. js my_first
  19. Mybatis set标签
  20. Egret动态设置按钮的图片

热门文章

  1. ubuntu开发项目不能执行热更新
  2. [JavaScript] audio在浏览器中自动播放
  3. 为你的Python程序加密
  4. 经典JS的HTML转义与反转义字符
  5. Python全栈开发之---redis数据库
  6. Token&amp;Cookies&amp;Session
  7. React常见的15个问题
  8. Error: No PostCSS Config found in... 报错 踩坑记
  9. alfs学习笔记-安装和使用blfs工具
  10. 当view为wrap_conten时获取一个view的具体宽高