[代码元]平衡二叉树-创新互联

题目描述
平衡二叉树(AVL树），是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为AVL树。 现在问题来了，给定AVL树的节点个数n，求有多少种形态的AVL树恰好有n个节点。
输入描述
一行一个整数T(T≤2000)表示数据组数
T行, 每行一个整数n(n≤2000)
输出描述
每行一个数字表示结果，由于结果巨大，输出它对109+7取余数的结果。
输入样例
1
10
输出样例
60

创新互联公司的客户来自各行各业，为了共同目标，我们在工作上密切配合，从创业型小企业到企事业单位，感谢他们对我们的要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。专业领域包括成都网站设计、网站建设、电商网站开发、微信营销、系统平台开发。

分析：

一棵树是平衡二叉树，其左子树有子树满足同样性质。
性质：左右子树的高度差最多为1
则我们可以推导出树与他的左右子树的关系。
设dp[i][j]表示有i个节点，高度为j时候的方案数。
显然当0个结点时，算一个方案，只有一个节点时也算一个方案。
即dp[0][0]=dp[1][1]= 1
状态转移方程课表示为如下：
左右子树同样高：dp[i][j]=dp[L][j - 1]+dp[R][j - 1]
左子树高右子树低：dp[i][j]=dp[L][j - 1]+dp[R][j - 2]
左子树低右子树高：dp[i][j]=dp[L][j - 2]+dp[R][j - 1]
其中节点的关系应该为i = L + R + 1

代码：

#includeusing namespace std;
const int N = 2010, mod = 1e9 + 7;

int n;
int dp[N][N];

int main()
{dp[0][0] = dp[1][1] = 1;
	for (int i = 2; i<= 2000; i ++ )
	{for (int j = 2; j<= 20; j ++ )
		{	for (int l = 0; l< i; l ++ )
			{		int r = i - 1 - l;
				dp[i][j] = (dp[i][j] + (long long)dp[l][j - 1] * dp[r][j - 1] % mod) % mod;
				dp[i][j] = (dp[i][j] + (long long)dp[l][j - 2] * dp[r][j - 1] % mod) % mod;
				dp[i][j] = (dp[i][j] + (long long)dp[l][j - 1] * dp[r][j - 2] % mod) % mod;
			}
		}
	}

	// for (int i = 0; i<= 20; i ++ )
	// {// 	for (int j = 0; j<= 15; j ++ )
	// 		printf("cnt = %d, h = %d, val = %d\n", i, j,dp[i][j]);
	// }

	int t;
	cin >>t;
	while (t -- )
	{scanf("%d", &n);

		int ans = 0;
		for (int i = 0; i<= 20; i ++ )
			ans = (ans + dp[n][i]) % mod;

		printf("%d\n", ans);
	}
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：[代码元]平衡二叉树-创新互联
分享URL：http://shouzuofang.com/article/dpdosc.html