题意

给出一棵二叉树前序和后序,求出有多少种中序的情况

思路

来源于这个luogu大佬

简要说一下

其实这道题是问有多少种中序遍历的情况

其实,只有叶节点只有一个时,才可能发生2种情况

• (后面有证明)

说明只需要找这个树有多少个 只有一个叶节点的节点 的个数

每一个 只有一个叶节点的节点 都会延伸两种情况

假设有 $t$ 个 只有一个叶节点的节点

所以答案是 $2^t$ 种情况

代码

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string a,b;
    int t=0;
    cin>>a>>b;
    for(int i=0;i<a.size();i++)
    {
        for(int j=1;j<b.size();j++)
        {
            if(a[i]==b[j] && a[i+1]==b[j-1])//只有一个叶节点的节点
            {
                t++;
            }
        }
    }
    cout<<(1<<t);//等价于2^t
    return 0;
}

证明

有两个叶节点的节点的中序不会有影响

前序
abc

后序
bca

树只有这种
  a
 / \
b   c

前序
ab

后序
ba

第一种树
  a
 /
b

第二种树
 a
  \
   b

前->前序遍历 中->中序遍历 后->后序遍历

思路：给定中能确定树的具体结构，是因为可以确定是左子树还是右子树，而之给定前和后，则不能确定，这就是会出现不同树结构的原因。

只有 前和 后 那么主要问题就是没有办法处理只有一个子树の情况，因为 这种情况 不知道子树 究竟是这个节点的左子树还是右子树，也就是说其实这道题要判断遍历中存在着多少个只有一棵子树的情况。对于前，如果一个结点的下个结点等于后中对应结点的前一个结点的话，那么这个结点就是根节点且其只有一个子树。sum初始化为1，出现一个只有一棵子树的情况，就把sum*2（每次会出现两种不同的情况，分别是出现左子树和出现右子树）。

还是蛮简单的

附AC代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
    char s[255],s1[255];
    scanf("%s",s);
    scanf("%s",s1);
    int len=strlen(s);
    int sum=1,k=0;
    for (int i=0;i<=len-1;i++)
    {
        k=0;
        for (int j=0;j<=len;j++)
        if (s[i]==s1[j]) 
        {
            k=j;    
            break;                                              //找它在后序遍历中出现的位置。ps：c+没pos函数真心不爽
        }
        if ((k!=0)&&(s1[k-1]==s[i+1])) sum<<=1;          //判断成功就sum=sum<<1
    }
    cout<<sum;
}