题解 P1229 【遍历问题】

青丝、暮成雪 · 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;
}