题目:
难度:Middle
相关话题:树
、动态规划
给定一个整数 n ,求以1 …n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3
输出: 5
解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路:
与NO.95
不同在于,这题不需要找出划分后具体的树,只需要保留结果,因此使用DP
。
dp[i]
表示从数量为i
有多少种划分,初始dp[0]=1
,即root
为null
就是1种划分。
dp[i]=dp[j]*dp[i-j-1]
,j
的范围为0<=j<i
,其中j
表示左子树的数量,i-j-1
表示右子树的数量。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
let dp=Array(n+1).fill(0)
dp[0]=1
for(let i=1;i<=n;i++){
for(let j=0;j<i;j++){
dp[i]+=dp[j]*dp[i-j-1]
}
}
return dp[n]
};
扩展阅读: