自动搬运

查看原文

来自洛谷，原作者为

	青丝、暮成雪 **

搬运于2025-08-24 21:22:40，当前版本为作者最后更新于2016-10-25 11:05:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

只有一个儿子 的节点 才会在知道 前序后序 的情况下有不同的中序遍历，所以将题目转化成找 只有一个儿子的节点个数。

可以很容易的找出这类节点在前序后序中出现的规律。（前序中出现AB，后序中出现BA，则这个节点只有一个儿子）

每个这类节点有两种中序遍历（及儿子在左，儿子在右）根据乘法原理中序遍历数为 2^节点个数 种

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int ans;
char str1[233],str2[233];
int main()
{
        scanf("%s",str1);
        scanf("%s",str2);
        for(int i=0;i<strlen(str1);i++)
         for(int j=1;j<strlen(str2);j++)
          if(str1[i]==str2[j]&&str1[i+1]==str2[j-1])
           ans++;
        printf("%d",1<<ans);
        return 0;
}