洛谷 P1229

题目链接

有4种结构。
对于只有一个儿子（度为1）的结点，其子节点在左/右不影响先序/后序的遍历顺序，总树数*2。即每多一个度为1的结点，二叉树数量翻倍。
即当先根序列为\(.....X Y.....，\)
后根序列为\(.........YX...\)时翻倍。求出这种结构的个数即可。

#include <bits/stdc++.h>

using namespace std;

int TreeNum(string pre, string post, int n) {
    if (n == 1) return 1;
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (pre[i] == post[j] && pre[i + 1] == post[j - 1]) ans *= 2;
        }
    }
    return ans;
}
int main()
{
    string pre, post;
    cin >> pre >> post;
    cout << TreeNum(pre, post, pre.size());
    return 0;
}