给定一个由节点值从 1 到 n 的 n 个节点。请问由多少种不同的方法用这 n 个节点构成互不相同的二叉搜索树。
请你输出有多少种方法。
例如:当n=2时有
数据范围:
import java.util.*; //dp[n] 表示长度为n的序列所构成的二叉搜索树的个数 //F(i,n)以i为根节点(i >= 1 && i <= n)所构成的二叉搜索树的个数 //[1,i-1]为右子树,[i+1,n]为左子树 //如果构成右子树的方法有m种,左子树的方法有n种,那么dp[i] = m*n //dp[n] 的结果就是不同的i为根节点所得到的方法之和 //例如 n = 3 //[1,2,3] //i = 1;没有左子树,右子树由2和3构成 F(1,3) = dp[0]*dp[2]=2 //i = 2;左子树由1构成,右子树由3构成 F(2,3) = dp[1]*dp[1]=1 //i = 3;左子树由1,2构成,右子树没有 F(3,3) = dp[2]*dp[0]=2 //dp[3] = F(1,3) + F(2,3) + F(3,3) = 5; public class Solution { public int BSTCount (int n) { int[] dp = new int[n + 1]; dp[0] = 1;//空树构成方法有一种 dp[1] = 1;//一个节点构成方法有一种 for(int i = 2;i <= n;i ++) { //dp[i]表示长度为i的序列所构成的二叉搜索树的个数 for(int j = 1;j <= i;j ++) { //j用来表示不同的根节点 dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } }
class Solution { public: int BSTCount(int n) { // dp[i]: 表示由i个互不相同的结点构成的 // 搜索二叉树的种树 int dp[n + 1]; // base case dp[0] = 1; dp[1] = 1; /* * 状态转移方程: * dp[i] = sum(dp[j - 1] * dp[i - j]), j = 1,...,i * */ for (int i = 2; i <= n; i++) { dp[i] = 0; for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } };
class Solution: def BSTCount(self , n: int) -> int: # write code here dp = [0] * (n+1) def dfs(n): if n == 0: return 1 if n == 1: dp[n] = 1 return 1 if dp[n] != 0: return dp[n] else: sum = 0 for i in range(1,n+1): left = i - 1 right = n - i y_a = dfs(left) y_b = dfs(right) sum += y_a * y_b dp[i] = sum return sum dfs(n) return dp[n]
package main //import "fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ func BSTCount( n int ) int { vis:=map[int]int{} var order func(int)int order=func(n int)int{ if _,ok:=vis[n];ok{ return vis[n] } if n<2{ return 1 } cnt:=0 for i:=1;i<=n;i++{ cnt+=order(i-1)*order(n-i) } vis[n]=cnt return cnt } return order(n) }