LeetCode 96 不同的二叉搜索树 题解
给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3
输出: 5
解释:
给定 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(n)
当 i 为根节点时,其左子树节点个数为 i-1 个,右子树节点为 n-i,则【注意是相乘,左半边组合数和右半边组合数相乘
】,G[i]其实表示的是连续的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)
用 2、3 构建,和用 1、2 构建,出来的种类数是一样的,因为参与构建的个数一样。
再比如 2,3,4 和 1,2,3 都是连着的三个数,构建出的 BST的种类数相同,属于重复的子问题。
定义 dp[i] :用连着的 i 个数,所构建出的 BST种类数;
base case:dp[0] = dp[1] = 1;
1、动态规划
public int numTrees(int n) {
//动态规划
int[] G = new int[n+1];
G[0] = 1;
G[1] = 1;
for(int i = 2; i < n+1; i++){
for(int j = 1; j <= i; j++){
G[i] += G[j-1]*G[i-j];//f(j) = G[j-1]*G[i-j]
}
}
return G[n];
}
2.递归
public int numTrees(int n) {
//递归 超时
if(n <= 1) return 1;
int num = 0;
for(int i = 1; i <= n; i++){
num += numTrees(i-1)*numTrees(n-i);
}
return num;
//记忆化递归
int[] mem = new int[n+1];
return num(mem,n);
}
public int num(int[] mem, int n){
if(n <= 1){
return 1;
}
if(mem[n] != 0){
return mem[n];
}
int res = 0;
for(int i = 1; i <= n; i++){
res += num(mem, i-1)*num(mem,n-i);
}
mem[n] = res;
return res;
}