AVL树是指左右子树的高度差不超过1,现在有一颗n个节点的
AVL树,问这样的树有多少种,比如n=10,有60种。
dp[n][h]表示n个节点高度为h的AVL树的个数。
dp[n][h] = dp[m1][h - 1] * dp[m2][h - 1] + 2 * dp[m3][h] * dp[m4][h - 1]
其中 m1 + m2 = n
m3 + m4 = n
其中h是logn级别的,所以总的时间复杂度大概是O(n ^ 2 logn)。
递归问题,有一颗n个节点的AVL树有多少种可以转化为问已经有了一个根节点,求n-1个节点的AVL树有多少种
如果只有一个节点,那么只有1种。