首页 > 试题广场 >

不同的二叉搜索树

[编程题]不同的二叉搜索树
  • 热度指数：14034 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个值n，能构建出多少不同的值包含1...n的二叉搜索树（BST）？
例如
给定 n = 3, 有五种不同的二叉搜索树（BST）

示例1

输入

3

输出

5
算法知识视频讲解
开通博客
头像 一叶浮尘
发表于 2020-04-11 12:34:42
给定一个值n，能构建出多少不同的值包含1...n的二叉搜索树（BST）？例如给定 n = 3, 有五种不同的二叉搜索树（BST） 这果然是一道easy的题目，因为纯靠数学推导，我们用f(n)表示对n的求解结果，在草稿上画画，你就知道f(1) = 1；f(2) = f(1)+f(1)；f(3) = 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 华科不平凡
发表于 2020-08-23 02:51:23
设值为n的情况下，可以组成f(n)个二叉搜索树，根据规律可知： f(0) = 1 f(1) = 1 f(n) += f(k-1)*f(n-k), 其中k=1,2,...n 显然，这是一个动态规划问题，实现如👇： // // Created by jt on 2020/8/23. // #inc 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 jing_zhong
发表于 2021-09-05 08:17:47
题目描述：给定一个值n，能构建出多少不同的值包含1...n的二叉搜索树（BST）？例如：给定 n = 3, 有五种不同的二叉搜索树（BST）示例1：        输入：3     展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 我是嫩叠
发表于 2024-10-05 20:05:41
class Solution { public: /** * * @param n int整型 * @return int整型 */ int numTrees(int n) { vector<int> dp(n 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 黑眼X
发表于 2025-10-10 17:39:24
import java.util.*; public class Solution { /** *使用 卡特兰数（Catalan）公式 * @param n int整型 * @return int整型 */ public in 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 you_config
发表于 2025-03-04 01:10:27
# # # @param n int整型 # @return int整型 # class Solution: def numTrees(self , n ): # write code here def function(k): i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 O-Precedence
发表于 2021-09-09 14:46:38
动态规划 public class Solution { public int numTrees (int n) { int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
难度：
93条回答 21771浏览

热门推荐

通过挑战的用户

查看代码

相关试题

不同的二叉搜索树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号