技术标签: pat甲级(树类型题)
1127 ZigZagging on a Tree (30 分)
Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in "zigzagging order" -- that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.
For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1
1 11 5 8 17 12 20 15
/**
本题题意:
给出一颗树的后序,中序遍历(可以推导出先序遍历构建出唯一树),
输出此唯一树的层序遍历不过是z字型输出, eg: 第一层 从右往 左输出,第二层从左往右输出
方法一:本题思路
利用结点下标索引进行排序,先将高度排序,(根节点位于第0层)偶数层从右往左(从大到小排序,) 奇数层从左往右(从小到大排序)
**/
/**
本题题意:
给出一颗树的后序,中序遍历(可以推导出先序遍历构建出唯一树),
输出此唯一树的层序遍历不过是z字型输出, eg: 第一层 从右往 左输出,第二层从左往右输出
本题思路
利用结点下标索引进行排序,先将高度排序,(根节点位于第0层)偶数层从右往左(从大到小排序,) 奇数层从左往右(从小到大排序)
**/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Node{
int h, index, data; //
};
int n;
vector<int> post, in;
vector<Node> zlevel;
bool cmp(Node a, Node b){
if(a.h != b.h)
return a.h < b.h;
else if(a.h % 2 == 0){ //当高度一致时,偶数层从右往左 (索引从大到小输出)
return a.index > b.index;
}else{ //奇数层,从左往右,(索引从 小 到 大 输出)
return a.index < b.index;
}
}
void preOrder(int postright, int inleft, int inright,int index, int h){
if(inleft > inright) return;
int i = inleft;
while(post[postright] != in[i]) i++;
// Node node = Node();//注意此步是 Node 没有new
// node.data = post[postright];
// node.h = h;
// node.index = index;
zlevel.push_back({h, index, post[postright]});
preOrder(postright - (inright - i) -1, inleft, i - 1, index * 2 + 1, h + 1);
preOrder(postright - 1, i + 1, inright, index * 2 + 2, h + 1);
}
int main(){
scanf("%d", &n);
in.resize(n);
post.resize(n);
for(int i = 0; i < n; i++){
scanf("%d", &in[i]);
}
for(int i = 0; i < n; i++){
scanf("%d", &post[i]);
}
preOrder(n - 1, 0, n - 1, 0, 0);
sort(zlevel.begin(), zlevel.end(), cmp);
for(int i = 0; i < n; i++){
if(i != 0)
printf(" ");
printf("%d", zlevel[i].data);
}
return 0;
}
方法二:
根据中序后序推出前序遍历通过链表建立树, 通过BFS 得到层次遍历,将结点按高度存放在result二维数组中
偶数高度 逆序输出 (从右向左)
奇数高度 正序输出(从左至右)
具体代码:
/**
思路 : 建立一颗树 将每层的结点通过BFS层序遍历分别放入二维向量数组 result[i]中(存放了在高度为i的全部结点)
当高度为偶数时输出 倒序输出
当高度为奇数时输出 正序输出
**/
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct Node{
Node *l, *r;
int data, h;
};
int n, cnt = 0; //cnt用来保证最后输出的格式
vector<int> post, in, result[35]; //
queue<Node *> q;
Node *preOrder(Node *root, int postright, int inleft, int inright, int h){
if(inleft > inright){
return nullptr;
}
int i = inleft;
while(post[postright] != in[i]) i++;
root = new Node();
root -> data = post[postright];
root -> h = h;
root -> l = preOrder(root -> l, postright -(inright - i) - 1, inleft, i - 1, h + 1);
root -> r = preOrder(root -> r, postright - 1, i + 1, inright, h + 1);
return root;
}
void levelOrder(Node *root){
q.push(root);
while(!q.empty()){
Node *n = q.front();
q.pop();
result[n->h].push_back(n->data);
if(n->l != nullptr)
q.push(n->l);
if(n->r != nullptr)
q.push(n->r);
}
}
int main(){
//k % 2 == 0表示从左至右遍历 k % 2 == 1 表示从右至左遍历
Node *root = nullptr;
scanf("%d", &n);
in.resize(n);
post.resize(n);
for(int i = 0; i < n; i++){
scanf("%d", &in[i]);
}
for(int i = 0; i < n; i++){
scanf("%d", &post[i]);
}
root = preOrder(root, n - 1, 0, n - 1, 0); //构建出一棵树
levelOrder(root); //进行层序遍历并就结点放入二维向量数组中
printf("%d", result[0][0]);
for(int i = 1; i < n; i++){
if(i % 2 == 1)
for(int j = 0; j < result[i].size(); j++)
printf(" %d", result[i][j]);
if(i % 2 == 0)
for(int j = result[i].size() - 1; j >= 0; j--)
printf(" %d", result[i][j]);
}
return 0;
}
当然也可以不用链表 静态用数组表示树:
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Node{
int lindex, rindex, h, index;
}node[35];
int n;
queue<Node> q;
vector<int> in, post, result[35];
int preOrder(int postright, int inleft, int inright, int h){
if(inleft > inright) return -1;
int i = inleft;
while(post[postright] != in[i]) i++;
node[postright].index = postright;
node[postright].h = h;
node[postright].lindex = preOrder(postright - (inright - i) - 1, inleft, i - 1, h + 1);
node[postright].rindex = preOrder(postright - 1, i + 1, inright, h + 1);
return postright;
}
void levelBFS(int postright){
q.push(node[postright]);
while(!q.empty()){
Node n = q.front();
result[n.h].push_back(post[n.index]);
q.pop();
if(n.lindex != -1){
q.push(node[n.lindex]);
}
if(n.rindex != -1){
q.push(node[n.rindex]);
}
}
}
int main(){
int n;
scanf("%d", &n);
in.resize(n);
post.resize(n);
for(int i = 0; i < n; i++){
scanf("%d", &in[i]);
}
for(int i = 0; i < n; i++){
scanf("%d", &post[i]);
}
preOrder(n - 1, 0, n - 1, 0);
levelBFS(n - 1);
printf("%d", result[0][0]);
for(int i = 1; i < n; i++){
if(i % 2 == 1)
for(int j = 0; j < result[i].size(); j++)
printf(" %d", result[i][j]);
if(i % 2 == 0)
for(int j = result[i].size() - 1; j >= 0; j--)
printf(" %d", result[i][j]);
}
return 0;
}
文章浏览阅读1.3k次。适用情况当你需要产生一堆相互之间没有交集的区间的时候当你听到重叠区间的时候解决思路:把每个区间按start排序,区间起始点为最小的start循环判断两个区间是否重叠(对于很多元素的对比,化简的思路是先只看两个元素怎么比较,然后循环迭代)重叠则找max end;不重叠则加入一个新区间元素抽象模式intervals.sort(<排序>)for <进入循环&g..._labuladong。合并区间
文章浏览阅读9.2k次,点赞5次,收藏8次。ExcelWriter writer = ExcelUtil.getWriter(true); writer.getStyleSet().setAlign(HorizontalAlignment.LEFT, VerticalAlignment.CENTER); //水平左对齐,垂直中间对齐writer.setColumnWidth(0, 40); //第1列40px宽writer.setColumnWidth(1, 15); //第2列15px 宽..._hutool excel导出设置单元格左对齐
文章浏览阅读130次,点赞2次,收藏3次。我们通常说的“内存”属于计算机部件中的( )。A:输出设备B:输入设备C:存储设备D:打印设备。_图形化编程scratch一级
文章浏览阅读765次,点赞18次,收藏21次。大家在求职的时候,肯定会遇到简历应该如何做,怎么做的问题,在这里我分享一下我的个人简历制作方法,我用这个方法制作的简历已经帮我拿到了心仪的offer简历的原则不。实景实拍,24年8月到期,20平米左右,有阳台,屋内独立卫浴,冰箱,水网免费,电费夏天整夜开空调的话一个月100元,额外赠送除图中的桌椅衣架。还有一个月就24年了,大家都有一个结果了吗,不管好与坏,至少比没结果要好 #你的秋招进行到哪一步了# #24届秋招同行攻略分享# #晒一晒我的offer# #秋。掌阅的钱是最高的,基本确定要去掌阅了。_京东24届采销offer
文章浏览阅读73次。Linux字符设别驱动结构cdev结构体struct cdev { struct kobject kobj; struct module *owner; const struct file_operations *ops; struct list_head list; dev_t dev; unsigned int count;};dev_..._linux 驱动struct list_head fu_list;
文章浏览阅读433次。新版彩虹工具网采用 ThinkPHP6.0 开发,自带 70 多个工具,包含站长工具、开发工具、实用工具、娱乐工具等分类,支持工具插件扩展,支持留言、用户注册登录、后台管理功能。目前已经更新到了 1.6 版本,新增了 QQ 等级查询、短视频解析等多个小工具。_彩虹工具网开源-支持工具插件扩展
文章浏览阅读1.2k次。作者简介Introduction邬书豪,车联网数据挖掘工程师 ,R语言中文社区专栏作者。微信ID:tsaiedu知乎专栏:https://www.zhihu.com/people/wu-shu-hao-67/activities往期回顾kaggle:数据科学社区调查报告(附学习视频)kaggle:员工离职预测(附学习视频)Kaggle:纽约的士旅程数据简要分析Kaggle:R可视化分析美国枪击案(_泰坦尼克号幸存者数据挖掘
文章浏览阅读2.4k次。在java中,同类型的模块代码结构往往是相似的。以Spring为例,一个工程都会包含controller,service,dao,modal等类型的代码。而dao用于数据库的访问,不同的表所对应的dao类都会有get,set,select,delete等操作,若手动编写dao,则这些dao有很多代码是类似的。于是希望自动生成这部分代码。一个非常直观的思路就是:写一个String模板,然后使用字符..._velocity依赖java
文章浏览阅读313次,点赞5次,收藏3次。使用AIML构建的WebQA Chatbot:一个交互式智能问答平台项目地址:https://gitcode.com/zhangbincheng1997/chatbot-aiml-webqa该项目是一个基于AIML(Artificial Intelligence Markup Language)的WebQA Chatbot,由开发者张昺成创建。它提供了一个直观的网页界面,让用户能够与Chat...
文章浏览阅读416次,点赞5次,收藏3次。探索ZjDroid:一款强大的Android逆向工程工具项目地址:https://gitcode.com/imlk0/ZjDroid项目简介ZjDroid 是一个由开发者社区贡献的开源项目,旨在为Android应用的逆向工程提供便利。它整合了多种实用工具,包括反编译器、代码查看器、资源提取器等,帮助开发者和安全研究人员深入理解Android应用的工作原理,进行漏洞检测、代码审计或二次开发。...
文章浏览阅读50次。springboot基于springboot和vue的阆中旅游文化网站。springboot基于springboot的智能ERP管理系统。springboot基于springboot的科研项目管理系统。springboot基于数据分析及推荐机制的篮球周边电商平台。springboot基于Vuejs的在线校园疫情管控服务平台。springboot基于springboot的产后护理系统。jsp基于java的车票购买与退订的管理系统的设计与开发。springboot基于JAVA的城镇社区服务管理平台。
文章浏览阅读852次。记录bios学习的点点滴滴,虽然已经学了很长时间才发出来,但就当是温故而知新吧,由于水平有限,难免存在错误,望指正,同时感谢CSDN提供的平台。1、LPC定义:Intel所定义的PC接口,将以往ISA BUS的地址/数据分离译码,改成类似PCI的地址/数据信号线共享的译码方式,信号线数量大幅降低,工作速率由PCI总线速率同步驱动,虽然改良过的LPC接口一样维持最大传输值16MB/s,不..._lpc chip low pin counter