前序与后序
   
　　我们对二叉树的前序与后序遍历都非常熟悉。在数据结构课中有一个经典问题就是：给定一个二叉树的中序遍历序列与后序序列，求一个前序序列，或者是给定中序遍历序列与前序序列，求一个后序序列。然而你无法确定中序序列，当给定前序与后序序列时。我们考查以下四种二叉树：

　　　　　　　　　　　　　

　　所有这些树都具有相同的前序序列，相同的后序序列。这种现象还不限于二叉树，对任意的m叉树也是一样。

输入：

　　输入包含多组。每组数据包含一行，形式为：m s1 s2，m表示给定的树为m叉树，s1是前序序列，s2是后序序列。
　　所有的前、后序序列都是由小写字母组成。对于所有数据，1≤m≤20，s1与s2的长度都在1到26之间（包含1与26），两个序列长度是一样的，序列中使用的字母是字母表中的前k个。输入以一行包含一个0为结束标志。

输出：

　　对于每个数据，你要输出一行，包含一个数，表示所有满足给定的前、后序序列的树的数目。测试数据保证使得所有的输出值不会超过一个32位有符号整数。你可以认为给定的前、后序序列，至少有一棵树满足。

Sample Input

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

Sample Output

　　4
　　1
　　45
　　207352860
　　
    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有