【LeetCode】不同的二叉搜索树 [M]（卡特兰数）

96. 不同的二叉搜索树 - 力扣（LeetCode）

一、题目

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

二、代码

class Solution {public int numTrees(int n) {return compute(n);}public int compute(int N) {// 过滤特殊值if (N < 0) {return 0;}if (N < 2) {return 1;}long a = 1;long b = 1;long c = 0;// 2nlong limit = N << 1;// 1、计算c(2N, N) = b / afor (long j = 1, i = N + 1; j <= N && i <= limit; j++, i++) {// 计算a：从1累乘到na *= j;// 计算b：从n+1一直累乘到2n  b *= i;// 求a和b的最大公因数，用来对a和b进行分数化简，避免在计算过程中溢出。// 如果这里不进行化简的话，当N比较大的时候就会出现数据溢出情况c = gcd(a, b);a /= c;b /= c; }// 2、计算公式3的计算结果// 公式3：k(n)= c(2n, n) / (n + 1)// c(n, m) = n(n-1)...(n-m+1) / m!// b：2n * (2n - 1) * ... * (2n - n + 1)   也就是从n+1一直累乘到2n// a：1 * 2 * ... * (n - 1) * n   也就是从1一直累乘到n// c(2N, N) = b / areturn (int) ((b / a) / (N + 1));}// 辗转相除法求最大公因数public long gcd(long a, long b) {long c = a % b;if (c != 0) {return gcd(b, c);} else {return b;}}
}

三、解题思路 

卡特兰数满足如下关系式：

k(0)= 1, k(1)= 1时，如果接下来的项满足：

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

或者

k(n)= C(2n, n) - C(2n, n-1)

或者

k(n)= C(2n, n) / (n + 1)

就说这个表达式，满足卡特兰数。

总的来说，需要剖析出这道题的本质：

假设n个节点存在二叉排序树的个数是G(n)，1为根节点，2为根节点，...，n为根节点，当1为根节点时，其左子树节点个数为0，右子树节点个数为n-1，同理当2为根节点时，其左子树节点个数为1，右子树节点为n-2，所以可得G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)。

明白了这道题的本质，发现了这个计算式子，就马上意识到这是一个卡特兰数的题目，直接用卡特兰数的计算公式计算结果即可。