题解：P1229 遍历问题

Doraeman · 2025-08-25 22:03:31 · 题解

思路

首先观察这三种遍历顺序的规律：

• 中序遍历：左根右（根把子节点隔开）；
• 先序遍历：根左右（两个子节点挨着）；
• 后序遍历：左右根（两个子节点挨着）。

如此一来就发现了问题：先、后序遍历的子节点都是挨着的。如果某棵子树只有 1 个子节点，只看先、后序遍历是无法区分出这是左子结点还是右子节点，对应在中序遍历中就会出现两种情况。

所以现在我们只需要统计只有 1 个子节点的子树的数量就可以了。

统计方法

如果一棵子树只有根和 1 个节点，假设根是 A，子节点是 B。表现方式是：

• 在先序遍历中为根在前：AB；
• 在后序遍历中为根在后：BA。

刚好是相邻且顺序相反。

按照这个规律，就可以循环找字符串 s_1,s_2 的 \forall i\isin[1,n),j\isin[1,n) 满足 s_i=s_{j+1} 且 s_{i+1}=s_j 的 (i,j) 组合的数量。

代码

#include<bits/stdc++.h>
using namespace std;

int main(){ 
    string s1, s2; 
    cin >> s1 >> s2;

    long long ans = 1;
    for(int i=0; i<s1.size()-1; i++)
        for(int j=0; j<s2.size()-1; j++)
            if(s1[i+1] == s2[j] && s1[i] == s2[j+1])
                ans *= 2;

    cout << ans;
}