LeetCode：96 不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

n = 3时，有5种    1         3       3       2      1     \       /        /         / \        \      3    2       1       1   3       2     /     /           \                      \    2    1             2                    3

思路：

假设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)∗(n−2)+...+G(n−1)∗G(0)

public class NumTrees { public int numTrees(int n) { int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = 1; if(n <= 1) { return 1; } //G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0) for (int i = 2; i < n + 1; i++) { for (int j = 0; j < i; j++) { //从2开始递推，递推的方式空间复杂度：O(n) dp[i] += dp[j] * dp[i - 1 - j]; } } return dp[n]; } public static void main(String[] args) { NumTrees numTrees = new NumTrees(); int i = numTrees.numTrees(5); System.out.println(i); } }