我们已经比较熟悉，在已知二叉树前序遍历和中序遍历或前序遍历和后序遍历的情况下如何求出这个特定的二叉树。然而已知前序遍历和后序遍历的情况下这个二叉树是不确定的，本篇博客研究在这种情况下的二叉树个数。
## 分析 前序遍历：根节点->左子树->右子树
后序遍历：左子树->右子树->左子树
为什么已知前序遍历和后序遍历的情况，二叉树是不确定。是因为对于某一根节点，如果它只有左子树或者右子树其中之一，那他就会出现两种情况。比如一颗二叉树的前序遍历为12，后序遍历为21。那这个二叉树可能为：
或者 
所以要求不确定二叉树的个数，只需要找到这种节点的个数就好。具体而言就是找到前序遍历和后序遍历中相同的节点，比如这里的1。再看前序遍历中这个节点的后一个节点和后序遍历中这个节点的下一个节点是否相同。每找到一个这样的节点，我们对count变量乘2就好（count初始为1）。
## 具体题目
代码如下： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#include<iostream>
#include<string>
using namespace std;
int main(){
string pre,post;
cin>>pre>>post;
int count = 1;
for(int i = 0;i<pre.length();i++){
int j = post.find(pre[i]);
if(i<pre.length()-1 && j>0 && pre[i+1] == post[j-1]){
count *= 2;
}
}
cout<<count;
}