二叉搜索树
二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
-
思路
仿佛是在找规律的一道题….看解析
随想录解析为什么是乘法？
分类计数和分步计数
```javascript
var numTrees = function(n) {
let dp =new Array(n+1).fill(0)
dp[0] =1for(let i=1;i<=n;i++){
for(let j=1;j<=i;j++){dp[i] +=dp[j-1]*dp[i-j]}
} return dp[n]
};
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$
<a name="nO3kw"></a>
# 卡特兰数
上文推导出来的递推公式在数学上称为卡特兰数<br /><br />
```javascript
var numTrees = function(n) {
let C = 1;
for (let i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return C;
};
时间复杂度 : O(n)
空间复杂度 : O(1)
若有收获，就点个赞吧
0 人点赞
