BSG白山极客挑战赛-AVL树

本文主要是介绍BSG白山极客挑战赛-AVL树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AVL树的种类

平衡二叉树(AVL树），是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为AVL树。现在问题来了，给定AVL树的节点个数n，求有多少种形态的AVL树恰好有n个节点。

Input

<span style="font-size: 14px;">一行，包含一个整数n。 (0 < n <= 2000)</span>

<span style="font-size: 14px;">
</span>

Output

<span style="font-size: 14px;">一行表示结果，由于结果巨大，输出它对1000000007取余数的结果。</span>

<span style="font-size: 14px;">
</span>

Input示例

<span style="font-size: 14px;">10</span>

Output示例

<span style="font-size: 14px;">60</span>

题意：如题。

题目链接：AVL树

解题思路：

首先题目限制是2000个结点，由二叉树的性质可知，最多也只能有20层（20层，2048个结点），所以可以考虑暴力！

然后一棵n个结点的AVL树，其左右两棵子树，也是AVL树，并且总结点数为n-1,而且层次差不能超过1，所以两棵子树也就是两种情况（层次差为0，层次差为1）。

dp[i][j]表示高度为i，结点数为j的所有AVL树的形态数。

就有状态转移方程：

dp[i][j]=dp[i-1][k]*dp[i-1][j-k-1]+ dp[i-1][k]*dp[i-2][j-k-1]*2

注意到左右子树层次不同时是可以交换左右子树的，但层次相同的时候循环k其实已经把左右对称的情况考虑了。

总结：

DP的训练还是太少太少了，竟然想到了DP，却不知道怎么列方程！！！不过也再一次见识到了DP的威力。

代码：

#include#include#include#include#define N 1000000007
using namespace std;
typedef long long ll;
ll dp[20][2005];
int main()
{
int i,j,k,n;
while(~scanf("%d",&n)){
memset(dp,0,sizeof(dp));
dp[1][1]=dp[0][0]=1;//边界情况
ll ans=dp[1][n];
for(i=2;i<20 ;i++  ){ //20层的节点数为2028
for(j=0;j<=n;j++){ //DP，总结点数位 n
for(k=0;k

这篇关于BSG白山极客挑战赛-AVL树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！