题目描述:
We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively,
you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below:
All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well.
输入:
Input will consist of multiple problem instances. Each instance will consist of a line of the form
m s1 s2
indicating that the trees are m-ary trees, s1 is the pre-order traversal and s2 is the post-order traversal.All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1 <= m <= 20 and the length of s1 and s2 will
be between 1 and 26 inclusive. If the length of s1 is k (which is the same as the length of s2, of course), the first k letters of the alphabet will be used in the strings. An input line of 0 will terminate the input.
输出:
For each problem instance, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instance. All output values will be within the range of
a 32-bit signed integer. For each problem instance, you are guaranteed that there is at least one tree with the given pre-order and post-order traversals.
样例输入:
2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
样例输出:
4
1
45
207352860
来源:
2008年上海交通大学计算机研究生机试真题
题目大意:对于n叉树,给出先序遍历和后续遍历,求可能的个数。
例如:
10 abc bca
根节点为a是确定的,接下来是 bc bc
可知b,c在同一级别,有C(10,2)=45 (10个位置中取两个)
2 abc cba
同样根节点为a,然后是 bc cb
b,c在两层 C(2,1) * C(2,1)=4
对于这个就有些复杂了,
13 abejkcfghid jkebfghicda
第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3)
再继续递归下去,直到字符串长度为1
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
int c[21][21];
int n;
long long test(string pre, string post) {
long long sum = 1;
int num = 0;
int k = 0, i;
pre.erase(pre.begin());
post=post.substr(0, post.length()-1);
while (k < pre.length()) {
for (i = 0; i < post.length(); i++)
if (pre[k] == post[i]) {
sum *= test(pre.substr(k, i - k + 1),
post.substr(k, i - k + 1));
//num代表串被分成了几段(例如 (bejkcfghid,jkebfghicd) = (bejk, cfghi, d) , num=3)
num++;
k = i + 1;
break;
}
}
//cout << pre << " " << post <<" " << t1 << " =" << num << endl << endl;
sum *= c[num][n]; //从n中取num个的取法个数
return sum;
}
void getsc() {
int i, j;
c[0][1] = c[1][1] = 1;
for (i = 2; i < 21; i++) {
c[0][i] = 1;
for (j = 1; j <= i; j++){
if (i == j)
c[j][i] = 1;
else
c[j][i] = c[j - 1][i - 1] + c[j][i - 1];
}
}
}
int main() {
freopen("in.txt", "r", stdin);
string pre, post;
getsc();
while ((cin >> n >> pre >> post) && n) {
cout << test(pre, post) << endl;
}
return 0;
}
分享到:
相关推荐
这是九度OJ-题目1509:树中两个结点的最低公共祖先的测试数据,input.txt是输入数据,output.txt是输出数据。
请为从1至n个结点命名: V1 V2 V3 V4 V5 V6 V7 V8 请输入8组相互依附的两结点: V1 V2 V2 V4 V4 V8 V8 V5 V2 V5 V1 V3 V3 V6 V3 V7 打印图的邻接矩阵: 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0...
使用vs2010编写,直接用vs2010打开加压后的.sln文件即可看到所有的代码,右键点击某一个cpp-“属性”-“从生成中排除”-“否”,即可运行该cpp,注意相应其他cpp该属性要设置为“是”。九度OJ上面的剑指Offer习题...
目前一共有下面几个项目 ConnWinBySSH 基于 JSCH 实现Linux远程连接windows并执行一些命令 ExtendDatabase 提高效率工具工程,扩展 ASE 数据库的data空间和log空间(默认增加 40G data和 10G log)。 DBLogMonitor ...
九度oj 题目1369:字符串的排列 剑指offer里面的题目 自己写的代码,供参考!
8.目标网页随机停留数秒后自动关闭; 9.目标网页随机位置、随机二次点击、深入点击,效果更真实; 10.随自己点击意愿和预期,设置日最大点击量和每一个小时内的最大点击量; 11.免费。挂机赚到一定的积分后即可...
九度智能seo优化软件是一款针对搜索引擎的点击类软件。软件适用于百度、谷歌、360搜索、搜狗、搜搜、淘宝、天猫等等搜索引擎,可以用来提高...绝对是专业人士必备的seo优化软件,您值得拥有! 九度智能seo优化软件截图
九度算法实现EXCEL排序 Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 对每个测试用例,首先输出1行“Case i:”,其中 i 是测试用例的编号(从1开始)。随后在 N 行中输出按要求排序后的结果...
完整可以用在二次开发,节约时间成本,
conn.asp 数据连接修改,站点名称和网址 del.asp 数据删除页,密码在文件里面修改 xg.mdb 数据库
8.目标网页随机停留数秒后自动关闭; 9.目标网页随机位置、随机二次点击、深入点击,效果更真实; 10.随自己点击意愿和预期,设置日最大点击量和每一个小时内的最大点击量; 11.免费。挂机赚到一定的积分后即可...
九度 ACM 很好的九度 ACM解题报告 不错 大家可以下下来看看 九度内推
九度OJ八皇后问题,主要是主对角线和副对角线的判断上面优化。在九度1140上面已经AC
ZJU考研机试真题 九度1006ZOJ问题
资源分享者,资源爱好者,我是浪杉,点我资料关注,每日不定时分享全网优质源码!
N皇后问题及其优化,主要是对角线和副对角线的判断上面的优化。输入要求的皇后数目n,输出有多少种排列的数目。 九度OJ1254已经AC
九度智能SEO优化软件是九度搜索引擎点击优化软件重新开发版,本是针对搜索引擎的SEO优化类软件,2016年10月正式上线。软件可像真人点击一样,自动点击百度、谷歌、360搜索、搜狗、搜搜、淘宝、天猫等搜索引擎内的...
九度求职经验系列之“实习生”篇.pdf 讲述了九度求职经验相关内容
由于九度搜索点击软件完全模仿人的自然行为进行点击,所以软件工作时,占用一台电脑,在挂机的同 时,不能干其他的事情。建议在闲暇时挂机,或有多余的电脑挂机,也可以在自己的电脑上,安装虚拟机,在虚拟机上运行...
此源码由九度网络科技有限公司提供 http://www.9dyou.com 1、使用技术 struts2 hibernate spring dwr 2、开发环境 tomcat6.0 jdk1.5 eclipse MySQL5.0 3、根据你的需要开放自主交易和寄售交易 4、在线订单即时...