不同的二叉搜索树
二 题目
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
};
根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。
三 解题思路
这是一道数学题：
1 2 5 14 42 132
1 --- 1:
2 --- 2: 1 * 3 - 1
3 --- 5: 2 * 4 - 1
4 --- 14: 3 * 5 - 1
5 --- 42: 4 * 6 - 1?
拿到题目的时候直接查看前 6 个测试用例，发现数字：1 2 5 14 42 132。
作为一枚纠结 Boy，看到这种情况想着一般都有通项公式，于是去搜索了下，发现：
所以它的通用公式是：!(2 * n) / !(1 + n) * !(n)，然后直接搞定这道题。
! 是阶乘的意思，!5 = 1 * 2 * 3 * 4 * 5
/**
* @param {number} n
* @return {number}
*/
const numTrees = (n) => {
let top = 1, bottomLeft = 1, bottomRight = 1;
for (let i = 2; i <= 2 * n; i++) {
top *= i;
}
for (let i = 2; i <= n + 1; i++) {
bottomLeft *= i;
}
for (let i = 2; i <= n; i++) {
bottomRight *= i;
}
return top / (bottomLeft * bottomRight);
};
console.log(numTrees(5));
四 统计分析
本题不需要统计分析。
五 套路分析
本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。
