洛谷P1229 遍历问题 题解

题目链接：P1229 遍历问题

题意：

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输出可能的中序遍历序列的总数，结果不超过长整型数。

首先这个遍历方式都知道吧

• 前序遍历：根左右
• 后序遍历：左右根

等等，如果根只有一个儿子怎么办？

好问题，我们并不知道他到底是左儿子还是右儿子

根据乘法原理，设有 $k$ 个结点 $u_i$ 满足 $\left|\left\{v \mid v \in \text{son}(u)\right\}\right|=1$

则答案为 $2^k$ 。直接 $O(n^2)$ 跑一下就好啦！

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2333)

int n,m,res;
char a[N],b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (a+1) >> (b+1); n=strlen(a+1); m=strlen(b+1); 
    for(int i=1; i<n; i++)
        for(int j=2; j<=m; j++)
            if(a[i]==b[j] && a[i+1]==b[j-1]) ++res;
    cout << (1ull << res) << '\n';
    return 0;
}