# P1229 遍历问题

## 题目描述

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

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

## 输入格式

共两行，第一行表示该二叉树的前序遍历结果 s_1，第二行表示该二叉树的后序遍历结果 s_2。

保证至少存在一棵二叉树满足给出的信息，s _ 1, s _ 2 中只含小写字母，且在某个字符串中不存在相同的字母。

## 输出格式

输出可能的中序遍历序列的总数，结果不超过 2^{63}-1。

##输入输出样例#1

###输入#1

```
abc                           
cba
```

###输出#1

```
4
```
定义 dfs(preL, preR, postL, postR)返回该区间对应的中序序列数。
根 = pre[preL]，在后序中找到根的位置 postRootIdx。
左子树长度 = postRootIdx - postL。
如果左子树长度 == 0（即 pre[preL+1] 不存在或 pre[preL+1] == post[postR-1] 吗？要仔细判断）—— 实际上判断条件：
前序第二个字符 pre[preL+1] 在后序中的位置如果是 postR-1（即后序的倒数第二个），则说明左子树为空或右子树为空？
其实应该是：前序第二个字符在后序中的位置如果是 postR-1，说明该节点只有一个孩子，且这个孩子是左孩子还是右孩子不确定。
此时，总方案数 = dfs(左子树) * dfs(右子树) * 2？
但注意，这里左子树长度是 1（那个孩子），右子树长度 0，所以 dfs(左子树) 是那个孩子的子树的中序方案数，dfs(右子树)=1，所以这一层方案数 = dfs(child) * 2。
如果左子树长度 > 0 且 pre[preL+1] != post[postR-1]，则正常划分左右，方案数 = dfs(left) * dfs(right)。
代码如下：
#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;

string pre, post;
vector<int> post_pos(26, -1);

ll solve(int preL, int preR, int postL, int postR) {
    if (preL > preR) return 1; 
    if (preL == preR) return 1;

    int root = pre[preL];

    int leftRoot = pre[preL + 1];
    int idx = post_pos[leftRoot - 'a'];

    int leftLen = idx - postL + 1;

  
    if (leftLen == 0 || pre[preL + 1] == post[postR - 1]) {
        // 此时 preL+1..preR 是唯一的孩子子树
        return solve(preL + 1, preR, postL, postR - 1) * 2;
    } else {
   
        ll leftCount = solve(preL + 1, preL + leftLen, postL, idx);
        ll rightCount = solve(preL + leftLen + 1, preR, idx + 1, postR - 1);
        return leftCount * rightCount;
    }
}

int main() {
    cin >> pre >> post;
    int n = pre.size();
    for (int i = 0; i < n; i++) {
        post_pos[post[i] - 'a'] = i;
    }
    ll ans = solve(0, n - 1, 0, n - 1);
    cout << ans << endl;
    return 0;
}