题目描述：
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例：
image.png
假设n个节点存在的二叉树个数为G(n)，令f(i)为以i为根的二叉树个数。
则G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)。当以i为根节点时，其左子树节点个数为i - 1，右子树结点个数为n - i,则有f(i) = G(i - 1) * G(n - i)。综上可得卡特兰数公式：
G(n) = G(0)G(n-1) + G(1)G(n-2) + ... + G(n-1)*g(0)
Java代码：
class Solution {
public int numTrees(int n) {
if(n == 0) return 0;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i < n + 1;i++)
for(int j = 1;j < i + 1;j++)
dp[i] += dp[j - 1] * dp[i - j];
return dp[n];
}
}
网友评论