1138. Postorder Traversal (25)
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 (<=50000), 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
后序遍历的顺序是先左右再树根,那么就一层一层来如果左子树不为空,那么答案一定在左子树,否则如果右子树不为空,那么答案一定在右子树,如果都不行,那么答案就是树根。
代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
int q[],z[];
int n;
int findpostfirst(int q1,int q2,int z1,int z2)
{
for(int i = z1;i <= z2;i ++)
{
if(z[i] == q[q1])
{
if(i != z1)return findpostfirst(q1+,q1+i-z1,z1,i-);
else if(i != z2) return findpostfirst(q1+i-z1+,q2,i+,z2);
else return q[q1];
}
}
}
int main()
{
cin>>n;
for(int i = ;i < n;i ++)
{
cin>>q[i];
}
for(int i = ;i < n;i ++)
{
cin>>z[i];
}
cout<<findpostfirst(,n-,,n-);
}
最新文章
- 基于Android的手机APP
- xml解析方法总结
- C语言 数组 列优先 实现
- JSon_零基础_001_将布尔类型数组转换为JSon格式字符串,返回给界面
- HDU1151Air Raid(二分图的最大匹配)
- iOS网络监测如何区分2、3、4G?
- ubuntu源码安装R语言
- myeclipse连接数据库遇到的几个问题
- windows版爬取csdn
- OpenStack 部署总结之:在CentOS 6.5上使用RDO单机安装icehouse(Ml2+GRE)
- 12-C语言字符串
- windows下C语言调用系统文件选择对话框
- 9 个用于移动APP开发的顶级 JavaScript 框架
- MySQL-悲观锁和乐观锁
- ipdb介绍及Tensor
- light oj 1254 - Prison Break 最短路
- Oracle 12c RAC
- python中逻辑运算符“+”的特殊之处
- 二、编译第一步 make xxx_defconfig
- fk输入地壳模型容易出错的地方