这题咋做呀……？一开始我的想法贼啦复杂也没法实现（实际就是不会）
后来看了dalao的想法之后明白了，如果在给定前后序的情况下中序遍历出现不同的情况，那么必然是树中有一些只有一个儿子的节点（因为这样树就是不定型的）
每出现这样一个节点，结果就会×2。
那我们还要去建树递归求只有一个儿子的节点有多少个吗……？咋求orz?
后来又看了dalao的想法，又领悟到，如果在前序遍历中出现了AB，在后序遍历中出现了BA，就说明这个节点只有一个儿子。所以我们暴力跑一遍字符匹配就可以……（神奇）
看一下代码（贼短）
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 50005; const int INF = 1000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } char a[M],b[M]; int len1,len2,ans; int main() { scanf("%s",a); scanf("%s",b); len1 = strlen(a) - 1,len2 = strlen(b) - 1; rep(i,0,len1) { rep(j,1,len2) if(a[i] == b[j] && a[i+1] == b[j-1]) ans++; } printf("%d ",1<<ans); return 0; }