有多少个不同的二叉搜索树

[编程题]有多少个不同的二叉搜索树

热度指数：835 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个由节点值从 1 到 n 的 n 个节点。请问由多少种不同的方法用这 n 个节点构成互不相同的二叉搜索树。

例如：当n=2时有

数据范围： $1 \le n \le 19 \$

示例1

输入

输出

示例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];
    }
}

发表于 2022-05-24 15:20:59 回复(0)

牛客541947765号

递归解，每次计算左子树的排列，右子树的排列

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]

发表于 2024-04-27 23:45:39 回复(0)

C++

牛客458436171号

动态规划解决问题，具体代码如下：

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];
    }
};

发表于 2022-05-10 11:36:26 回复(0)

唐氏综合征

遍历到第 i 个节点，选择 j 节点作为根节点，依次递推找到所有可能性：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    public int BSTCount (int n) {
        // write code here
        int[] dp = new int[n + 1];
        dp[0] = 1; // 空树也算一种情况
        dp[1] = 1;

        // 以第 j 个节点为根节点的情况, i 是节点总数
        // 左边的节点所有可能性：dp[j-1], 因为已经计算过，再计算右节点的所有构建树 dp[i-j]
        // 累加起来就是当前的节点数可以构成的最大数量

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
        }
    }

发表于 2024-04-30 12:48:44 回复(0)

小谷围做题家

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)
}

发表于 2023-03-14 21:17:42 回复(0)