题目描述：
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
代码：
#include <stdio.h>
#include <string.h>
int result;
int Cal(int n,int m)//计算组合数,从n个中选m个;
{
if(m==n)
return 1;
else if (m==1)
return n;
else
return Cal(n-1,m)+Cal(n-1,m-1);
}
void Count(char *A,char *B,int num)
{
int n=strlen(A);
if(n==1)
return ;
A=A++;//忽略第一个;
B[n-1]='\0';//忽略最后一个;
int count=0;
while(*A)
{
int i=0;
char newA[27],newB[27];
while(A[0]!=B[i])
{
newA[i]=A[i];
newB[i]=B[i];
i++;
}
newA[i]=A[i];
newB[i]=B[i];
newA[i+1]='\0';
newB[i+1]='\0';
count++;//统计在当前这一层有多少个子树;
A=A+i+1;
B=B+i+1;
Count(newA,newB,num);
}
result=result*Cal(num,count);
}
int main()
{
int n;
char A[27],B[27];
//freopen("data.in","r",stdin);
while(scanf("%d",&n)!=EOF)
{
scanf("%s%s",&A,&B);
result=1;
Count(A,B,n);
printf("%d\n",result);
}
}
作者提醒：
这个题目的分析估计都被写烂了，我这里就简单的说明一下，其实觉得他们写了好多好多很浅显的东西，希望我的分析能够给大家减轻点负担，虽然我也是看别人的分析之后才更加理解这个题目。
分析如下：
已知前序和后序，
1：我们先知道的，肯定是字符串第一个会等于最后一个
2：既然是m叉树，那么我们就要分析m叉树中有几个还有子树，然后我们就需要分析子树的由来。
3：子树中又有子树，这个就是组合数学中的一件事情分步完成，则最终的组合为步步相乘。
所以问题的关键就在于我怎么知道子树的存在呢？
找子树的过程，把前一个字符串记为A，后一个记为B
先执行步骤1，即跳过第一个字符，A=A+1；
然后把取出A的第一个字符A[0]，在B中找，直到B[i]==A[0]，就是一个子树
就分析下面最简单的两个吧
2 abc cba 4
2 abc bca 1
第一个，执行步骤1，剩下bc和cb，找完第一次就发现找完了，所以就只有1个子树，然后再去对bc进行查找
第二个，执行步骤1，剩下bc和bc，找到两个子树
下面还有一个别人的acm的 给你复制过来了
分析
题目大意：对于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
代码：
解法1
#include <iostream>
#include <string.h>
#include <string>
#include <stdio.h>
using namespace std;
char str1[30],str2[30];
string pre,post;
int n;
int c[23][23];
//组合数计算
void initc(){
c[1][0] = c[1][1] = 1;
for(int i=2; i<23; i++){
c[i][0] = 1;
for(int j=1; j<=i; j++){
c[i][j] = c[i-1][j] + c[i-1][j-1];
}
}
}
int getCnt(string left,string right){
int cnt=0;
int res = 1;
if(left.size() <= 1) return n; //只有一个元素，可以放置n个位置
for(int i=0; i<left.length();){
int j=i;
while(j<left.length() && right[j] != left[i]) j++ ;
//一层的单个叶子节点不考虑
if(j>i)
res *= getCnt(left.substr(i+1,j-i), right.substr(i,j-i));
cnt++;
i = j+1;
}
res *= c[n][cnt];
return res;
}
int main() {
freopen("in.txt","r",stdin);
initc();
while(cin >> n ){
if(!n) break;
cin >> pre >> post;
int ans = 1;
if(pre.length() > 1)
ans = getCnt(pre.substr(1,pre.length()-1), post.substr(0, pre.length()-1) );
cout << ans << endl;
}
return 0;
}
解法2
#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++; //num代表串被分成了几段(例如 (bejkcfghid,jkebfghicd) = (bejk, cfghi, d) )
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() {
string pre, post;
getsc();
while ((cin >> n >> pre >> post) && n) {
cout << test(pre, post) << endl; //printf("%ld\n",test(pre,post));
}
return 0;
}