江西省建设厅网站资质升级查询,制作表格的步骤,市政道路毕业设计代做网站,如何建设自己的摄影网站96. 不同的二叉搜索树 - 力扣#xff08;LeetCode#xff09; 一、题目
给你一个整数 n #xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种#xff1f;返回满足题意的二叉搜索树的种数。
示例 1#xff1a; 输入#xff1a;n 3
输出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从n1一直累乘到2n b * i;// 求a和b的最大公因数用来对a和b进行分数化简避免在计算过程中溢出。// 如果这里不进行化简的话当N比较大的时候就会出现数据溢出情况c gcd(a, b);a / c;b / c; }// 2、计算公式3的计算结果// 公式3k(n) c(2n, n) / (n 1)// c(n, m) n(n-1)...(n-m1) / m!// b2n * (2n - 1) * ... * (2n - n 1) 也就是从n1一直累乘到2n// a1 * 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)。
明白了这道题的本质发现了这个计算式子就马上意识到这是一个卡特兰数的题目直接用卡特兰数的计算公式计算结果即可。
