九度OJ 1044：Pre-Post（先序后序）（n叉树、递归）

本文主要是介绍九度OJ 1044：Pre-Post（先序后序）（n叉树、递归），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：701

解决：398

题目描述：

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

样例输出：

来源：

2008年上海交通大学计算机研究生机试真题

思路：

求对于m叉树而言其每层的叶子节点的组合方式有多少种。

由先序和后序序列其实可以却确定每一层的叶子节点的个数，以及哪些是这一层的叶子节点，唯一不确定的就是这些节点的位置（但是由先序可以确定这些叶子节点相对位置是确定的），比如第i层有n个叶子节点（由先序和后序结合判定出），那么这层就有c(n,m)种组合方式，然后确定某个叶子节点的子树，对其进行递归求解。

代码：

#include <stdio.h>
#include <string.h>#define M 20
#define N 26int m;long long C(int m, int k)
{int i;long long c = 1;for (i=m; i>k; i--)c *= i;for (i=m-k; i>0; i--)c /= i;return c;
}long long prepost(char s1[], char s2[])
{int len = strlen(s1);if (len == 0 || len == 1)return 1;char root;int c;char sch1[M][N+1], sch2[M][N+1];int i, j, k;c = 0;i = 1;while (i < len){root = s1[i];j = i-1;k = 0;do{sch1[c][k] = s1[i];sch2[c][k] = s2[j];k++;i++;} while (s2[j++] != root);sch1[c][k] = '\0';sch2[c][k] = '\0';c++;}long long count = C(m, c);for (i=0; i<c; i++)count *= prepost(sch1[i], sch2[i]);return count;
}int main(void)
{char s1[N+1], s2[N+1];while (scanf("%d", &m) != EOF){scanf("%s%s", s1, s2);//printf("%lld\n", C(6, 2));printf("%lld\n", prepost(s1, s2));}return 0;
}
/**************************************************************Problem: 1044User: liangrx06Language: CResult: AcceptedTime:0 msMemory:912 kb
****************************************************************/

这篇关于九度OJ 1044：Pre-Post（先序后序）（n叉树、递归）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！