首页 > 试题广场 >

Pre-Post

[编程题]Pre-Post

热度指数：2258 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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.

示例1

输入

2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda

输出

算法知识视频讲解

Trenchy

#include <stdio.h>
#include <string.h>

int m;

int count(int l1,int h1,char *s1,int l2,int h2,char *s2,int n){
if(n<=1) return 1;
l1=l1+1;//去掉父节点
h2=h2-1;
n=n-1;
int k,l=1,h=1,c=1;
for(int i=0;i<m;i++){//拆分出子树，进行几次循环，就有几颗子树
char key=s1[l1];
l=l*(i+1);//子树在分支上的次序固定，分布情况是排列组合问题
h=h*(m-i);
for(k=l2;k<=h2;k++) if(s2[k]==key) break;
c=c*count(l1,k-l2+l1,s1,l2,k,s2,k-l2+1);
n=n+l2-k-1;
l1=k-l2+l1+1;
l2=k+1;
if(k==h2) break;
}
return h*c/l;
}

int main(){
int n,c;
char s1[27]={'\0'};
char s2[27]={'\0'};
while(scanf("%d %s %s",&m,s1,s2)!=EOF){
n=strlen(s1);
c=count(0,n-1,s1,0,n-1,s2,n);
printf("%d\n",c);
}
}

发表于 2022-01-13 00:41:15 回复(0)