← 返回题目

题库练习遍历问题

← 上一题下一题 →

A2944 | $遍历问题$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：![](/uploads/acgo/image/1ad4eaed379eafdf_3096e62ee546.png) 所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输入格式

共两行，第一行表示该二叉树的前序遍历结果 $s_1$，第二行表示该二叉树的后序遍历结果 $s_2$。

输出格式

输出可能的中序遍历序列的总数，结果不超过 $2^{63}-1$。

输入输出样例

输入 #1

abc                           
cba

输出 #1

C++ 编辑器

输入

输出