PAT 甲级 1020 Tree Traversals

时间:2022-08-26 22:26:42

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的更多相关文章

  1. PAT 甲级 1020 Tree Traversals &lpar;二叉树遍历)

    1020. Tree Traversals (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue Suppo ...

  2. PAT 甲级 1020 Tree Traversals &lpar;25分&rpar;(后序中序链表建树,求层序)&ast;&ast;&ast;重点复习

    1020 Tree Traversals (25分)   Suppose that all the keys in a binary tree are distinct positive intege ...

  3. PAT 甲级 1020 Tree Traversals &lpar;25 分&rpar;(二叉树已知后序和中序建树求层序)

    1020 Tree Traversals (25 分)   Suppose that all the keys in a binary tree are distinct positive integ ...

  4. 【PAT】1020 Tree Traversals &lpar;25&rpar;(25 分)

    1020 Tree Traversals (25)(25 分) Suppose that all the keys in a binary tree are distinct positive int ...

  5. PAT Advanced 1020 Tree Traversals &lpar;25 分&rpar;

    1020 Tree Traversals (25 分)   Suppose that all the keys in a binary tree are distinct positive integ ...

  6. PAT 甲级 1086 Tree Traversals Again &lpar;25分&rpar;(先序中序链表建树,求后序)&ast;&ast;&ast;重点复习

    1086 Tree Traversals Again (25分)   An inorder binary tree traversal can be implemented in a non-recu ...

  7. 【PAT】1020&period; Tree Traversals &lpar;25&rpar;

    Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and i ...

  8. PAT 甲级 1086 Tree Traversals Again

    https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024 An inorder binary tree ...

  9. PAT甲级——A1086 Tree Traversals Again

    An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example ...

随机推荐

  1. 利用私有的库MobileCoreServices检测正在安装的应用

    利用的私有库检测正在安装的app 分为两步:第一,通过placeholderApplications获得所有的正在安装的app的信息 第二,遍历正在安装的app的信息,根据名称获得你想检测的app是否 ...

  2. 开始用Word 2013来写博客

    第一步:如果从未发布过博客文章的话,需要在菜单里面选这里添加博客账号   第二步:选择正确的设置   第三步:写完博客之后,按这里就可以发布了!   如果以后需要写新的博客的话,还可以直接点这里:   ...

  3. react 和 ractive的区别

    前面进项目的时候同事说项目在用react. 我没有深究,实际中发现是ractive.js.后来发现其实另有一个react.js.和ractive.js是有区别的.不过也有相似的地方. react项目的 ...

  4. 在 Area 中使用RouteAttribute 定义路由&comma; 并支持多语言

    业务上的一个需求, 同一页面, 两种不同的使用方法, 为了区分这两种需求, 需要加一个参数到 URL 中,不改路由的话, 是这样: http://localhost:16269/en-US/Forwa ...

  5. Java集合框架之LinkedList-----用LinkedList模拟队列和堆栈

    LinkedList的特有方法: (一)添加方法 addFisrt(E e):将指定元素插入此列表的开头.//参数e可以理解成Object对象,因为列表可以接收任何类型的对象,所以e就是Object对 ...

  6. Android studio启动后卡在refreshing gradle project(包解决)

    这个问题几乎每个刚使用Android studio的同学都会碰到过,网上有各式各样的方法,有的说使用本地gradle,我试过多次,每次启动android studio时还是会检查更新,所以根本上解决的 ...

  7. Python爬虫入门之正则表达式

    在前面我们已经搞定了怎样获取页面的内容,不过还差一步,这么多杂乱的代码夹杂文字我们怎样把它提取出来整理呢?下面就开始介绍一个十分强大的工具,正则表达式! 1.了解正则表达式 正则表达式是对字符串操作的 ...

  8. Git 基础 —— 安装 配置 别名 对象

    Git 基础学习系列 Git 基础 -- 安装 配置 别名 对象 Git 基础 -- 常用命令 Git 基础 -- 常见使用场景 Git基础 -- Github 的使用 Git 安装 Git下载地址 ...

  9. MySQL学习【第六篇sql语句下】

    一.select高级用法 1.传统连接(只能内连接,取交集,效率最慢) 1.根据两张表查询张三成绩 select t1.sname,t2.mark from t1,t2 where t1.sid=t2 ...

  10. sklearn 中的交叉验证

    sklearn中的交叉验证(Cross-Validation) sklearn是利用python进行机器学习中一个非常全面和好用的第三方库,用过的都说好.今天主要记录一下sklearn中关于交叉验证的 ...