前序后序难题
| 成绩 | 100 | 开启时间 | 2020年06月11日 星期四 22:45 |
| 折扣 | 0.8 | 折扣时间 | 2020年06月11日 星期四 22:45 |
| 允许迟交 | 是 | 关闭时间 | 2020年06月11日 星期四 22:45 |
| 输入文件 | PrePost.in | 输出文件 | PrePost.out |
【题目描述】前序后序难题（PrePost）POJ 1240
通常来说，不能通过前序和后序遍历序列确定一颗二叉树的中序遍历序列，例如图4.37所示的这4颗二叉树：
图4.37
所有的这4颗二叉树都有着相同的前序和后序遍历序列。这个现象不仅在二叉树中存在，也同时在m叉树中普遍存在。
【输入格式】
输入包含多组测试数据。每组包含一行，按照m，s1，s2的形式，表示这是一颗m叉树，s1是这颗树的前序遍历序列，s2是后序遍历序列，两个序列只包含小写字母。对于所有的测试数据，1≤m≤20，1≤s1≤26，1≤s2≤26。如果s1的长度为k（当然s2的长度也为k），那么序列中一定且只会出现前k个小写字母。当输入的一行只有一个数字0时，表示输入结束。
【输出格式】
对于每组测试数据，需要输出一行，表示所给出的前序和后序遍历所表示的树一共有多少种可能。保证答案不会超过32位整型数据的范围。对于每种测试数据，保证至少存在一棵树满足所给出的前序和后序遍历序列。
【输入样例】
2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
0
【输出样例】
4
1
45
207352860