PAT_A1138#Postorder Traversal
2024-08-31 05:30:08
Source:
Description:
Suppose that all the keys in a binary tree are distinct positive integers. Given the preorder and inorder traversal sequences, you are supposed to output the first number of the postorder 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 (≤ 50,000), the total number of nodes in the binary tree. The second line gives the preorder 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 first number of the postorder traversal sequence of the corresponding binary tree.
Sample Input:
7
1 2 3 4 5 6 7
2 3 1 5 4 7 6
Sample Output:
3
Keys:
- 二叉树的遍历
Attention:
- 建树的过程实质上也是遍历二叉树的过程
Code:
/*
Data: 2019-05-26 20:53:20
Problem: PAT_A1138#Postorder Traversal
AC: 16:20 题目大意:
假设二叉树中各个结点权值不同且为正;
给出先序和中序遍历,求后序遍历中的第一个结点
*/ #include<cstdio>
const int M=1e5;
int pre[M],in[M],f=; void Travel(int preL, int preR, int inL, int inR)
{
if(preL > preR)
return;
int k;
for(k=inL; k<=inR; k++)
if(in[k]==pre[preL])
break;
int numLeft = k-inL;
Travel(preL+, preL+numLeft, inL,k-);
Travel(preL+numLeft+, preR, k+,inR);
if(f){
printf("%d\n", in[k]);f=;
}
} int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif int n;
scanf("%d", &n);
for(int i=; i<n; i++)
scanf("%d", &pre[i]);
for(int i=; i<n; i++)
scanf("%d", &in[i]);
Travel(,n-,,n-); return ;
}
最新文章
- Spring MVC初始化参数绑定
- 12、产品经理要阅读的书籍 - IT软件人员书籍系列文章
- 【原创-算法-实现】异步HTTP请求操作
- jQuery 的三种获取值的方式
- 如何选择开源许可证&;如何修改项目使其符合某种开源许可证
- 微信公开课PRO版张小龙演讲全文
- arm汇编--ubuntu12.04 安装arm-linux交叉编译环境
- showMonth
- web应用的发布
- (八)Android广播接收器BroadcastReceiver
- Lua 垃圾收集机制
- JavaWeb(一)Servlet中乱码解决与转发和重定向的区别
- JQ编写楼层效果
- windows下更改mysql数据储存物理目录
- 3--TestNG多线程
- iOS-带图片的二维码的生成(QRCode)
- Java工具类——UUIDUtils
- 远程桌面管理工具Remote Desktop Connection Manager
- 2017/05/08 java 基础 随笔
- Python几种并发实现方案的性能比较
热门文章
- N天学习一个Linux命令之mkdir
- [转]十五天精通WCF——第六天 你必须要了解的3种通信模式
- 数据结构之---C语言实现最短路径之Dijkstra(迪杰斯特拉)算法
- UVa 263 - Number Chains
- 王立平--java se的简单项目创建以及具体解释
- 2014年百度之星程序设计大赛 - 资格赛 第一题 Energy Conversion
- samba笔记
- luogu2763 试题库问题 二分匹配
- [NOIP 2016] 蚯蚓
- python-day3 元组(tuple),列表(list),字典(dict)