/ / 题库 /

遍历问题

遍历问题

测试数据来自 wjszez/1972

问题描述:
我们都很熟悉二叉树的前序、中序、后序遍历,在数据结构中常提出这样的问题:已知一棵二叉树的前序和中序遍历,求它的后序遍历,相应的,已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历,你却不能确定其中序遍历序列,考虑如下图中的几棵二叉树:

所有这些二叉树都有着相同的前序遍历和后序遍历,但中序遍历却不相同。

输入文件:
输入数据共两行,第一行表示该二叉树的前序遍历结果s1,第二行表示该二叉树的后序遍历结果s2。

输出文件:
输出可能的中序遍历序列的总数,结果不超过长整型数。

样例输入:
abc
bca

样例输出:
4

信息

ID
2009
难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者