Skip to content

1113: travel

题目

题目描述

我们都很熟悉二叉树的前序、中序和后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历序列,求它的后序遍历序列,相应的已知一棵二叉树的后序遍历和中序遍历序列,你也能求出它的前序遍历。 然而,给定一棵二叉树的前序和后序遍历序列,你却不能确定其中序遍历序列。并且这一现象不仅出现在二叉树中,对M叉树亦如此。

输入格式

输入数据共一行,格式为:m s1 s2 表示该树为m叉树,其前序遍历序列为s1,其后序遍历序列为s2,s1和s2由小写字母构成。 1≤m≤20,且s1与s2的长度相等且不超过26,若它们的长度为k,则前k个小写字母将不重复地出现在s1与s2中。

输出格式

输出可能的树的形态的总数,结果不超过长整型数。 注意,下面两棵树就是不同形态:

样例输入

text 10 abc bca

样例输出

text 45

数据范围

见输入格式。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!