Problem
平衡二叉树(AVL树),是指左右子树高度差至多为1的二叉树,并且该树的左右两个子树也均为AVL树。 现在问题来了,给定AVL树的节点个数n,求有多少种形态的AVL树恰好有n个节点。
Solution
f[n][h]代表n个节点,高度为h的AVL树的种数。
f[n][h]=f[n-i-1][h-1]×f[i][h-1]+2×f[n-i-1][h-2]×f[i][h-1] 0<=k<n
左右子树都是h-1层,或者左右子树一个是h-1层,一个是h-2层,由于不对称要×2。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| #include<stdio.h> #include<bits/stdc++.h> using namespace std; #define ll long long const int mod=1000000007; int n; ll f[2020][22],ans; int main(){ scanf("%d",&n); f[0][0]=1; f[1][1]=1; for(int i=2;i<=20;i++){ for(int j=2;j<=n;j++){ for(int k=0;k<j;k++){ f[j][i]=(f[j][i]+f[j-1-k][i-1]*f[k][i-1])%mod; f[j][i]=(f[j][i]+2*f[j-1-k][i-2]*f[k][i-1])%mod; } } } for(int i=0;i<=20;i++){ ans=(ans+f[n][i])%mod; } printf("%lld\n",ans); return 0; }
|