`

Unique Binary Search Trees

阅读更多
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.
   1           3     3      2       1
     \         /     /        / \        \
      3     2     1       1  3       2
     /      /        \                      \
   2      1          2                     3


考察二叉树的种类,卡特兰数的例子。这里要注意的是空树也属于二叉搜索树。代码如下:
public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}
分享到:
评论

相关推荐

    python-leetcode题解之096-Unique-Binary-Search-Trees

    题目描述:096-Unique Binary Search Trees(不同的二叉搜索树)是LeetCode上的一个算法问题,编号96。问题的目标是找出给定节点数n的所有不同的二叉搜索树(BST)的个数。二叉搜索树是一类特殊的二叉树,其中每个...

    python-leetcode题解之095-Unique-Binary-Search-Trees-II

    今天,我们聚焦于LeetCode上的第95题“Unique Binary Search Trees II”,该题目要求参与者使用给定的数值序列构建所有可能的不同二叉搜索树(BSTs)。二叉搜索树是一种特殊的二叉树,其中每个节点都满足以下性质:...

    c语言-leetcode题解之0095-unique-binary-search-trees-ii.zip

    LeetCode作为一个广泛使用的在线编程平台,提供了众多关于二叉搜索树的问题,其中问题编号0095 “Unique Binary Search Trees II”是一个典型的问题,旨在考察解题者对二叉搜索树性质的理解以及递归思维的应用。...

    c语言-leetcode题解之0096-unique-binary-search-trees.zip

    而“unique binary search trees”这一概念,则通常出现在动态规划的上下文中。这个问题在LeetCode上被标记为第96题,要求编写程序来计算给定数字n所能构成的不同形状的唯一二叉搜索树(BST)的数量。这里的关键在于...

    js-leetcode题解之95-unique-binary-search-trees-ii.js

    在LeetCode中,问题编号95的题目就是要求生成给定节点数的所有可能的唯一二叉搜索树(Unique Binary Search Trees II)。该问题是一个典型的递归问题,可以通过深度优先搜索(DFS)算法来解决。 问题的描述是这样的...

    js-leetcode题解之96-unique-binary-search-trees.js

    代码示例中的js_leetcode题解之96-unique-binary-search-trees.js,会提供一个具体的解决方案。这个解决方案会涉及如何初始化dp数组,如何通过循环和乘法操作来填充数组,以及最终返回dp[n]的结果,即为题目所求的...

    陈越、何钦铭-数据结构作业16:Complete Binary Search Tree完全二叉搜索树

    Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled ...

    算法学习笔记

    - Unique Binary Search Trees:不同的二叉搜索树的个数。 - Happy Number:一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,也可能是无限...

    leetcodepython001-Algorithm:关于数据结构和算法的问题(Leetcode、编程之美和课程作业)

    leetcode python 001 Algorithm 用python和java解决了Leetcode上部分问题,另外还有对常规算法和机器学习算法的一些实现,例如用遗传算法解物流配送问题。...Search Trees Python 2017/11/28 Medium 09

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    数据结构与算法题解

    - **UniqueBinarySearchTrees** - 计算不同的二叉搜索树的数量。 - **UpdateBits** - 更新一个整数的某些位。 - **FastPower** - 快速幂运算。 - **HashFunction** - 设计算法的哈希函数。 - **Count1inBinary**...

    算法-leetcode-剑指offer上的题很多

    - **唯一二叉搜索树(Unique Binary Search Trees)**: 不同的二叉搜索树的数量。 #### 位操作技巧 - **更新位(Update Bits)**: 在一个整数中更新若干位。 - **快速幂(Fast Power)**: 快速计算一个数的幂。 #### ...

    leetcode答案-LeetCodeSolution:这是LeetCode网站问题的解决方案集

    Unique Binary Search Trees 本题参考了 里面的*How Many Binary Trees Are There?*章节。 The first few terms: C(0) = 1 C(1) = C(0)C(0) = 1 C(2) = C(0)C(1) + C(1)C(0) = 2 C(3) = C(0)C(2) + C(1)C(1)

    leetcode添加元素使和等于-Leetcode-tree:力码树

    leetcode添加元素使和等于 Leetcode-tree 94题 Binary ...Search Trees 这道题我们使用了动态规划的方法。说到动态规划我们这里先总结一下动态规划类型的题该如何做。 动态规划题目特点: 计数型: -有

    CBST.rar_The Keys_bst

    Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled ...

    leetcode卡-leetcode:Python

    【描述】中的"Unique Binary Search Trees"提到了一种特定的LeetCode问题,即"唯一的二叉搜索树"。这个问题要求计算给定整数n的所有不同结构的二叉搜索树的数量。二叉搜索树是一种特殊的二叉树,其中每个节点的左...

    Algorithms and Data Structures - Niklaus Wirth

    - **Binary B-Trees**: Special case of B-trees optimized for binary trees. **Priority Queues**: Data structures that manage items based on priority, often implemented using heaps. This detailed ...

    leetcode1477-coding-for-fun:编码乐趣

    96.unique-binary-search-trees.cpp [TODO] 70. 爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 最长公共子序列.cpp 第 5 天: [待办事项] leetcode/221。 最大平方....

    EhLib 6.3 Build 6.3.176 Russian version. Full source included.

    Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an element to other parental record. Component TDBGridEh supports to show the tree-type ...

Global site tag (gtag.js) - Google Analytics