C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 1412 AVL树的种类

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;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/52032/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!