二叉树的递归遍历（dp）

已知先序遍历跟后序遍历，求这样的二叉树的个数

对于一条链来说，先序跟后序的区别就是正着念跟倒着念的区别，利用这条性质，不停的将先序遍历得到的串去掉第一个后进行划分（同时后序遍历得到的串去掉最后一个）

#include <bits/stdc++.h>
using namespace std;
const int N=30;
int dp[N][N][N][N];
char x[N], y[N];
int dfs(int la, int ra, int lb, int rb)
{
if(la>ra) return 0;
if(x[la]!=y[rb]) return dp[la][ra][lb][rb]=0;
if(la==ra) return 1;
if(dp[la][ra][lb][rb]=!-1) return dp[la][ra][lb][rb];
int ans=0;
//左右子树均不为空
for(int i=1; la+i<ra; i++)
{
ans+=dfs(la+1,la+i,lb,lb+i-1) * dfs(la+i+1,ra,lb+i,rb-1);
}
//左子树或者右子树为空
ans+=2*dfs(la+1,ra,lb,rb-1);
return dp[la][ra][lb][rb]=ans;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%s%s", x+1, y+1);
memset(dp, -1, sizeof(dp));
printf("%dn", dfs(1, strlen(x+1), 1, strlen(y+1)));
}
return 0;
}
/*
99
ABCD
DCBA
ABCDEFG
DECFBGA
*/

最后

以上就是微笑向日葵为你收集整理的二叉树的递归遍历（dp）的全部内容，希望文章能够帮你解决二叉树的递归遍历（dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。