A22658.遍历问题

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

输入格式

共两行,第一行表示该二叉树的前序遍历结果 s1s_1,第二行表示该二叉树的后序遍历结果 s2s_2

输出格式

输出可能的中序遍历序列的总数,结果不超过 26312^{63}-1

输入输出样例

  • 输入#1

    abc                           
    cba
    

    输出#1

    4

说明/提示

输出可能的中序遍历序列的总数,结果不超过 26312^{63}-1

首页