https://pintia.cn/problem-sets/994805342720868352/problems/994805485033603072
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the level order traversal sequence of the corresponding binary tree. 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.
Sample Input:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Sample Output:
4 1 6 3 5 7 2
代码:
#include <bits/stdc++.h>
using namespace std; int N;
vector<int> in, post, level(100000, -1); void rec(int root, int st, int en, int index) {
if(st > en) return;
int i = st;
while(i < en && in[i] != post[root]) i ++;
level[index] = post[root];
rec(root - 1 - en + i, st, i - 1, 2 * index + 1);
rec(root - 1, i + 1, en, 2 * index + 2);
} int main() {
scanf("%d", &N);
in.resize(N), post.resize(N);
for(int i = 0; i < N; i ++)
scanf("%d", &post[i]);
for(int i = 0; i < N; i ++)
scanf("%d", &in[i]); rec(N - 1, 0, N - 1, 0);
int cnt = 0;
for(int i = 0; i < level.size(); i ++) {
if(level[i] != -1) {
if(cnt) printf(" ");
printf("%d", level[i]);
cnt ++;
}
if(cnt == N) break;
}
return 0;
}
已知后序中序求层序遍历的结果
vector<int> level(100000, -1); 这句话很有必要
PAT 甲级 1020 Tree Traversals的更多相关文章
-
PAT 甲级 1020 Tree Traversals (二叉树遍历)
1020. Tree Traversals (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Suppo ...
-
PAT 甲级 1020 Tree Traversals (25分)(后序中序链表建树,求层序)***重点复习
1020 Tree Traversals (25分) Suppose that all the keys in a binary tree are distinct positive intege ...
-
PAT 甲级 1020 Tree Traversals (25 分)(二叉树已知后序和中序建树求层序)
1020 Tree Traversals (25 分) Suppose that all the keys in a binary tree are distinct positive integ ...
-
【PAT】1020 Tree Traversals (25)(25 分)
1020 Tree Traversals (25)(25 分) Suppose that all the keys in a binary tree are distinct positive int ...
-
PAT Advanced 1020 Tree Traversals (25 分)
1020 Tree Traversals (25 分) Suppose that all the keys in a binary tree are distinct positive integ ...
-
PAT 甲级 1086 Tree Traversals Again (25分)(先序中序链表建树,求后序)***重点复习
1086 Tree Traversals Again (25分) An inorder binary tree traversal can be implemented in a non-recu ...
-
【PAT】1020. Tree Traversals (25)
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and i ...
-
PAT 甲级 1086 Tree Traversals Again
https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024 An inorder binary tree ...
-
PAT甲级——A1086 Tree Traversals Again
An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example ...
随机推荐
-
利用私有的库MobileCoreServices检测正在安装的应用
利用的私有库检测正在安装的app 分为两步:第一,通过placeholderApplications获得所有的正在安装的app的信息 第二,遍历正在安装的app的信息,根据名称获得你想检测的app是否 ...
-
开始用Word 2013来写博客
第一步:如果从未发布过博客文章的话,需要在菜单里面选这里添加博客账号 第二步:选择正确的设置 第三步:写完博客之后,按这里就可以发布了! 如果以后需要写新的博客的话,还可以直接点这里: ...
-
react 和 ractive的区别
前面进项目的时候同事说项目在用react. 我没有深究,实际中发现是ractive.js.后来发现其实另有一个react.js.和ractive.js是有区别的.不过也有相似的地方. react项目的 ...
-
在 Area 中使用RouteAttribute 定义路由, 并支持多语言
业务上的一个需求, 同一页面, 两种不同的使用方法, 为了区分这两种需求, 需要加一个参数到 URL 中,不改路由的话, 是这样: http://localhost:16269/en-US/Forwa ...
-
Java集合框架之LinkedList-----用LinkedList模拟队列和堆栈
LinkedList的特有方法: (一)添加方法 addFisrt(E e):将指定元素插入此列表的开头.//参数e可以理解成Object对象,因为列表可以接收任何类型的对象,所以e就是Object对 ...
-
Android studio启动后卡在refreshing gradle project(包解决)
这个问题几乎每个刚使用Android studio的同学都会碰到过,网上有各式各样的方法,有的说使用本地gradle,我试过多次,每次启动android studio时还是会检查更新,所以根本上解决的 ...
-
Python爬虫入门之正则表达式
在前面我们已经搞定了怎样获取页面的内容,不过还差一步,这么多杂乱的代码夹杂文字我们怎样把它提取出来整理呢?下面就开始介绍一个十分强大的工具,正则表达式! 1.了解正则表达式 正则表达式是对字符串操作的 ...
-
Git 基础 —— 安装 配置 别名 对象
Git 基础学习系列 Git 基础 -- 安装 配置 别名 对象 Git 基础 -- 常用命令 Git 基础 -- 常见使用场景 Git基础 -- Github 的使用 Git 安装 Git下载地址 ...
-
MySQL学习【第六篇sql语句下】
一.select高级用法 1.传统连接(只能内连接,取交集,效率最慢) 1.根据两张表查询张三成绩 select t1.sname,t2.mark from t1,t2 where t1.sid=t2 ...
-
sklearn 中的交叉验证
sklearn中的交叉验证(Cross-Validation) sklearn是利用python进行机器学习中一个非常全面和好用的第三方库,用过的都说好.今天主要记录一下sklearn中关于交叉验证的 ...