1210. 二叉树
Constraints
Time Limit: 1 secs, Memory Limit: 32 MB
Description
在众多的数据结构中，二叉树是一种特殊而重要的结构，有着广泛的应用。二叉树或者是一个结点，或者有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。
遍历一棵二叉树就是按某条搜索路径巡访其中每个结点，使得每个结点均被访问一次，而且仅被访问一次。最常使用的有三种遍历的方式：
１．前序遍历：若二叉树为空，则空操作；否则先访问根结点，接着前序遍历左子树，最后再前序遍历右子树。
２．中序遍历：若二叉树为空，则空操作；否则先中序遍历左子树，接着访问根结点，最后再前中遍历右子树。
３．后序遍历：若二叉树为空，则空操作；否则先后序遍历左子树，接着后序遍历右子树，最后再访问根结点。
例如图(1)所示的二叉树：
前序遍历的顺序是ABCD，中序遍历的顺序是CBAD，后序遍历的顺序是CBDA。
对一棵二叉树，如果给出前序遍历和中许遍历的结点访问顺序，那么后序遍历的顺序是唯一确定的，也很方便地求出来。但如果现在只知道前序遍历和后序遍历的顺序，中序遍历的顺序是不确定的，例如：前序遍历的顺序是ABCD，而后序遍历的顺序是CBDA，那么就有两课二叉树满足这样的顺序（见图(1)和图(2)）。
现在的问题是给定前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。
Input
整个输入有两行，第一行给出前序遍历的访问顺序，第二行给出后序遍历的访问顺序。
二叉树的结点用一个大写字母表示，不会有两个结点标上相同字母。输入数据不包含空格，且保证至少有一棵二叉树符合要求。
Output
输出一个整数，为符合要求的不同形态二叉树的数目。
Sample Input
ABCD CBDA
Sample Output
2
/*
如果只知道二叉树的前序遍历结果与后序遍历结果，是无法确定唯一的二叉树
我们注意到的是，当一结点只有一个孩子时，无论他是左孩子还是右孩子，他们的前序遍历与后序遍历结果都是一样的
这就是无法唯一确定的原因，一棵树中有多少个这种情况，就会有2*^多少种中序遍历结果
现在就要找前序遍历为AB，后序遍历为BA的情况
*/
#include<iostream>
#include<string>
using namespace std;
int main()
{
string pre,post;
cin>>pre>>post;
int count=1;
int temp=post.size()-1; //对于前序遍历与后序遍历，前序的第一个结点与后序的最后一个结点是一样的
int size=post.size();
for(int i=1;i<size;i++)
{
int j=post.find(pre[i]);
if(j==temp-1)count*=2;
temp=j;
}
cout<<count;
return 0;
}