洛谷P1229 遍历问题（c嘎嘎）

题目链接：P1229 遍历问题 - 洛谷 | 计算机科学教育新生态

题目难度：普及/提高

解题思路：   对于一个二叉树，并不是给定前序（根左右）后序（左右根)就无法确定二叉树，只是说，在某些情况下，不能唯一确定。下面直接给出结论 。

结论：当只有一个儿子 的节点 才会在知道 前序后序 的情况下有不同的中序遍历。

所以本题转化为成找只有一个儿子的节点个数。

前序中出现ab，后序中出现ba，则这个节点只有一个儿子,每个这类节点有两种中序遍历（及儿子在左，儿子在右）根据乘法原理中序遍历数为 2^节点个数种

下面奉上代码部分：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1,s2;int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 0;cin >> s1 >> s2;for(int i=0; i<s1.size(); i++)for(int j=1; j<s2.size(); j++){if(s1[i] == s2[j] && s1[i + 1] == s2[j - 1]){t++;}}cout<<(1<<t);return 0;
}