题目链接
有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;
}