专栏首页刷题笔记【2020HBU天梯赛训练】7-37 玩转二叉树

【2020HBU天梯赛训练】7-37 玩转二叉树

7-37 玩转二叉树

【2020HBU天梯赛训练】7-30 树的遍历的姊妹题

这道题给中序遍历和前序遍历 相反的层序输出

姊妹题给中序遍历和后序遍历 层序输出。

给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式:

输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式:

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

输入样例:

7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

输出样例:

4 6 1 7 5 3 2

直接改的上一题代码完成的这道题哈

#include<iostream>
#include<vector>
using namespace std;
int preorder[33];
int inorder[33];
vector<vector<int>> levels(33);
void init(int postbg,int postend,int inbg,int inend,int level){
	if(postbg>postend)return;
	int r=preorder[postbg];
	int t=0;
	while(inorder[inbg+t]!=r)t++;
	levels[level].push_back(r);
	init(postbg+1,postbg+t,inbg,inbg+t-1,level+1); 
	init(postbg+t+1,postend,inbg+t+1,inend,level+1);
	return;
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>inorder[i];
    for(int i=0;i<n;i++)cin>>preorder[i];
	init(0,n-1,0,n-1,0);
	cout<<levels[0][0];
	for(int i=1;i<33;i++){
		for(int l=levels[i].size()-1;l>=0;l--) cout<<" "<<levels[i][l];
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode第 164 场周赛】回顾

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【2020HBU天梯赛训练】7-30 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    韩旭051
  • 【LeetCode程序员面试金典】面试题 10.01. Sorted Merge LCCI

    You are given two sorted arrays, A and B, where A has a large enough buffer at t...

    韩旭051
  • 剑指offer No.4 重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

    week
  • P1378 油滴扩展

    题目描述 在一个长方形框子里,最多有N(0≤N≤6)个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必...

    attack
  • 【GPLT】L2-006 树的遍历

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 面向对象(四)-值类型与引用类型详解

    类型被分为两种:值类型(整数,bool struct char 小数)和引用类型(string 数组 自定义的类,内置的类)。

    雷潮
  • 5929 亲戚

    题目描述 Description 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规...

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 练习7-9 计算天数

    输入在一行中按照格式“yyyy/mm/dd”(即“年/月/日”)给出日期。注意:闰年的判别条件是该年年份能被4整除但不能被100整除、或者能被400整除。闰年的...

    C you again 的博客
  • 仿qq最新侧滑菜单

    为了后续对这个项目进行优化,比如透明度动画、背景图的位移动画,以及性能上的优化。 我把这个项目上传到github上面,请大家随时关注。 github地址 htt...

    xiangzhihong

扫码关注云+社区

领取腾讯云代金券