3770 - 二叉树遍历
二叉树的前序、中序、后序遍历介绍如下：
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根 结点，然后遍历左子树，最后遍历右子树。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历 左子树，再访问根结点，最后遍历右子树。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历 左子树，然后遍历右子树，最后遍历根结点。
在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的， 已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序 和后序，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：
所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。
Input
首先输入一个 T(T <= 20), 表示数据集数目。
每组数据，第一行表示该树的前序遍历结果，第二行表示该树的后序遍历结果。树上两个字符不会 相同。输入的字符集合为{a-z}，长度不超过26。
Output
对于每组数据，输出包含一个不超过长整型的整数，表示可能的中序遍历序列的总数。
Examples
Input
1 abc cba
Output
4
Solution C++
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; string _a, _b; long long dp[30][30][30][30]; long long DP(int l, int r, int a, int b) { // cout << l << " " << r << " " << a << " " << b << endl; // if (l > r) return 1; if (dp[l][r][a][b] != -1) return dp[l][r][a][b]; if (_a[l] != _b[b]) return dp[l][r][a][b] = 0; if (l == r ) return dp[l][r][a][b] = 1; long long res = DP(l+1, r, a, b-1) * 2; for (int k=l+1; k<r; k++) { res += DP(l+1, k, a, a+k-l-1) * DP(k+1, r, a+k-l, b-1); } return dp[l][r][a][b] = res; } int main () { int T; cin >> T; while (T--) { cin >> _a >> _b; memset(dp, -1, sizeof(dp)); cout << DP(0, _a.size()-1, 0, _b.size()-1) << endl; } return 0; }