卡塔兰序列_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

🌸分析

给定一个有序序列1..n,为了构建出一棵二叉搜索树，我们可以遍历每个数字
i,将该数字作为树根，所以如果求1..n的所有可能。

• 我们只需要把1作为根节点, [] 空作为左子树, [2 .. n]的所有可能作为右
  子树。

• 2作为根节点，[1] 作伪左子树, [3..n]的所有可能作为右子树。

• 3作为根节点，[1， 2 ]的所有可能作为左子树，[4 … n]的所有可能作为右子树，然后左子树和右子树两两组合。

• 4作为根节点[1 ，2，3]的所有可能作为佐子树，[5 .. n]的所有可能作为右子树,然后佐子树和右子树两两组合。

• …….

• n作为根节点，[ 1…. n]的所有可能作为左子树，[]作为右子树。

由此可见，原问题可以分解成规模较小的两个子问题，子问题的解可以复用。
因此，我们可以想到使用递归、动态规划来求解本题。

🌸解法一：递归搜索

按照以上分析的思路，假设n个节点存在二叉排序树的个数是G(n),令f(i)为以i为根的二叉搜索树的个数,当找到其中一个数i的左子树可能的数量G(i - 1),右子树可能的数量是G(n - i),那么f(i) = G(i - 1) * G(n - i)

public int numTrees(int n) {
	if(n == 0) {
		return 0;
	}
	
	return dfs(n);
}
private int dfs(int n) {
	// TODO Auto-generated method stub
	int res = 0;	//保存可能的个数
	//递归要素：终止条件
	if(n == 0 || n == 1) {
		return 1;
	}
	
	//将[1..n]作为根节点
	for(int i = 1; i <= n; i++) {
		//拿到所有可能的左子树[]、[1..i)区间内个数
		int leftCount = dfs(i - 1);
		//拿到所有可能的右子树[]、(i...n]区间内个数
		int rightCount = dfs(n - i);
		
		//将个数进行排列组合
		res += leftCount * rightCount;
	}
	
	return res;
}

🌸解法二： 记忆化递归搜索

由于递归的分叉，所以会导致很多重复解的计算，所以使用 memoization 技术，把递归过程中求出的解保存起来，第二次需要的时候直接拿即可。

public int numTrees2(int n) {
	if(n == 0) {
		return 0;
	}
	Map<Integer, Integer> memory = new HashMap<>();
	return dfs2(n, memory);
}
private int dfs2(int n, Map<Integer, Integer> memory) {
	// TODO Auto-generated method stub
	//如果已经被计算过的数，直接取出返回
	if(memory.containsKey(n)) {
		return memory.get(n);
	}
	
	int res = 0;	//保存可能的个数
	//递归要素：终止条件
	if(n == 0 || n == 1) {
		return 1;
	}
	
	//将[1..n]作为根节点
	for(int i = 1; i <= n; i++) {
		//拿到所有可能的左子树[]、[1..i)区间内个数
		int leftCount = dfs2(i - 1, memory);
		//拿到所有可能的右子树[]、(i...n]区间内个数
		int rightCount = dfs2(n - i, memory);
		
		//将个数进行排列组合
		res += leftCount * rightCount;
	}
	//记录保存的值
	memory.put(null, res);
	
	return res;
}

🌸解法三：动态规划

根据前面的解法一定义：

G(n)= f(1)+ f(2)+ f(3)+ f(4)+...+ f(n)

f(i)=G(i-1)*G(n-i)

G(n) 从f(1…n)得到，f(i) 递归依赖于G(n)，)G(n) 和序列的内容无关，只和序列的长度有关

到此，我们从小到大计算G函数即可,因为G(n)的值依赖于G(0)…G(n- 1)。

java

public int numTrees3(int n) {
	if(n == 0) {
		return 0;
	}		
	int[] dp = new int[n + 1];
	dp[0] = 1;
	dp[1] = 1;
	
	//将[1..n]作为根节点,已记录dp[1]=1
	for(int i = 2; i <= n; i++) {
		for(int j = 1; j <= i; j++) {
			//记算左边j - 1个数可能的个数，右边i-j个数可能的个数
			dp[i] += dp[j - 1] * dp[i - j];
		}
	}
	return dp[n];
}

🌸解法三：动态规划空间优化

源自HeII0W0rId，可移步

🌸解法四： 卡塔兰公式

综合G(n)、f(i) 的 公式可以得到

G(n)= G(0)* G(n-1)+G(1)*(n-2)+...+ G(n-1)*G(0)

这就觉得这个公式挺眼熟的。

下面给出卡塔兰公式的定义

令h(0)=1,h(1)=1，卡塔兰数满足递归式:
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + .. + h(n-1)h(0) (其中n>=2),这是n阶递推关系;
还可以化简为1阶递推关系:如h(n)=(4n-2)/(n+1)*h(n-1)(n>1) h(0)=1
该递推关系的解为:
$$
h(n)=\frac{C(2n,n)}{n+1}=\frac{P(2n,n)}{(n+1)!}=\frac{(2n!)}{(n!*(n+1)!)}(n=1,2,3,…)
$$

$$
C_n = \frac{(2n)!}{(n+1)!n!}
$$

$$
C_0=1, C_{n+1} = \frac{2(2n+1)}{n+2}C_n
$$

public int numTrees5(int n) {
    long catalan = 1;
    for (int i = 0; i < n; ++i) {
    	catalan = catalan * 2 * (2 * i + 1) / (i + 2);
    }
    return (int) catalan;
}

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！