洛谷-P1229 遍历问题题解

题目链接：https://www.luogu.com.cn/problem/P1229

题目大意

给定一棵二叉树的前序遍历和后序遍历序列（每个字符唯一），要求计算可能的中序遍历序列的总数。

注意：仅凭前序 + 后序 无法唯一确定一棵二叉树（特别是当某个节点只有一个子节点时，无法判断是左孩子还是右孩子），因此可能存在多种合法的中序遍历。

核心观察

1. 前序与后序的特点

前序：根 → 左子树 → 右子树
后序：左子树 → 右子树 → 根

设前序为 pre，后序为 post，长度为 n。

pre[0] 和 post[n-1] 都是整棵树的根节点。
若树只有一个节点（n == 1），则中序只有一种可能。

2. 关键难点：单子树的歧义性

当一个节点只有一个子节点时：

在前序中，下一个元素是该子节点；
在后序中，倒数第二个元素也是该子节点；
但我们无法判断这个子节点是左孩子还是右孩子！

而这两种情况会导致不同的中序遍历（左孩子在根前，右孩子在根后）。

因此，每出现一次“只有一个子节点”的情况，答案就要 ×2。

3. 如何判断是否有两个子树？

从前序中，根是 pre[l1]，那么左子树的根是 pre[l1+1]（如果存在左子树）。

我们在后序中找到 pre[l1+1] 的位置 index，那么：

后序中 [l2, index] 是左子树的后序；
所以左子树大小 = index - l2 + 1；
如果 index == r2 - 1，说明左子树包含了除根外的所有节点，即没有右子树 → 此时只有一个子树，产生歧义！

特别地：当 index == r2 - 1，意味着整个子树除了根只有一个分支，此时无法区分是左还是右，方案数 ×2，并递归处理剩下的部分。

否则，左右子树都存在，无歧义，分别递归左右子树，方案数相乘。

算法设计：递归分治

定义函数：

ll process(int l1, int r1, int l2, int r2)

表示：

前序区间 [l1, r1]
后序区间 [l2, r2]
返回该子树对应的可能中序序列数量

递归逻辑：

边界条件：若 l1 == r1（只有一个节点），返回 1。
找到前序中左子树的根：pre[l1 + 1]
在后序 [l2, r2-1] 中查找该值的位置 index
关键判断：如果 index == r2 - 1：说明除了根，其余都在一个子树中（只有一个孩子）歧义！方案数 = process(整个子树) * 2否则：左子树大小 = index - l2 + 1递归左子树：[l1+1, l1+1 + (index-l2)] 和 [l2, index]递归右子树：剩余部分总方案数 = 左方案 × 右方案

代码解析

#include<iostream>
#include<string>
using namespace std;

typedef long long ll;

string str1, str2; // str1: 前序, str2: 后序

ll process(int l1, int r1, int l2, int r2)
{
    if (l1 == r1) return 1; // 只有一个节点

    // 找前序中左子树的根（即 pre[l1+1]）在后序中的位置
    int index = l2;
    while (index <= r2 && str2[index] != str1[l1 + 1])
        index++;

    // 如果该节点是后序中倒数第二个（即 r2-1），说明只有一个子树
    if (index == r2 - 1)
        return process(l1 + 1, r1, l2, r2 - 1) * 2;

    // 否则，左右子树都存在
    int leftSize = index - l2 + 1;
    ll leftWays = process(l1 + 1, l1 + leftSize, l2, index);
    ll rightWays = process(l1 + leftSize + 1, r1, index + 1, r2 - 1);
    return leftWays * rightWays;
}

int main()
{
    cin >> str1 >> str2;
    cout << process(0, str1.size() - 1, 0, str2.size() - 1);
    return 0;
}