96. Unique Binary Search Trees

淡淡的烟草味﹌ 2024-04-07 11:53 84阅读 0赞

Given an integer `n`, return *the number of structurally unique **BST'**s (binary search trees) which has exactly* `n` *nodes of unique values from* `1` *to* `n`.

**Example 1:**

![9d5e5b463ee27c06dac2aa90c957e636.jpeg][]

Input: n = 3
    Output: 5

**Example 2:**

Input: n = 1
    Output: 1

**Constraints:**

*  `1 <= n <= 19`

题目：给一个正整数n,求由节点1~n组成的二叉搜索树结构有几个

思路：由于是二叉搜索树，因此只要根节点确定了，左右子树节点个数也就确定。从1到n遍历，分别从1到n作为根节点，求左右子树的结构个数相乘。最后的加和即为结果。为减少重复运算，用vector数组dp记录i个节点的结构数。代码：

class Solution {
    private:
        vector<int> dp;
    public:
        int helper(int n){
            if(dp[n] > 0) return dp[n];
            for(int i = 0; i<n; i++){
                dp[n] += helper(i) * helper(n-i-1);
            }
            return dp[n];
        }
        int numTrees(int n) {
            dp.resize(n+1, 0);
            dp[0] = 1;
            return helper(n);
        }
    };

[9d5e5b463ee27c06dac2aa90c957e636.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/788f32747bb34902bf619c73592911d0.jpeg

发表评论取消回复

表情：

评论列表（有 0 条评论，84人围观）

还没有评论，来说两句吧...

相关阅读

相关 96. Unique Binary Search Trees

Given an integer `n`, return the number of structurally unique BST's (binary search tree

淡淡的烟草味﹌/ 2024年04月07日 11:53/ 0 赞/ 85 阅读

相关 leetcode 95. Unique Binary Search Trees II | 96. Unique Binary Search Trees

95. Unique Binary Search Trees II [https://leetcode.com/problems/unique-binary-search

布满荆棘的人生/ 2022年09月10日 03:13/ 0 赞/ 171 阅读

相关 LeetCode96——Unique Binary Search Trees

LeetCode96——Unique Binary Search Trees 结构不同的二叉树个数，比起上一题，因为只要求出个数，我们只需要利用卡特兰数的递推式子构造动归

た入场券/ 2022年08月21日 00:04/ 0 赞/ 21 阅读

相关【LeetCode】96. Unique Binary Search Trees 解法及注释

96. Unique Binary Search Trees Total Accepted: 80679 Total Submissions: 216054 Difficul

悠悠/ 2022年07月28日 09:56/ 0 赞/ 145 阅读

相关 [leetcode-动态规划]--96. Unique Binary Search Trees

Question 96. Unique Binary Search Trees > Given n, how many structurally unique BST’s (

Love The Way You Lie/ 2022年07月12日 04:23/ 0 赞/ 142 阅读

相关 [leetcode-动态规划]--96. Unique Binary Search Trees

Question 96. Unique Binary Search Trees > Given n, how many structurally unique BST’s (

阳光穿透心脏的1/2处/ 2022年07月12日 04:23/ 0 赞/ 147 阅读

相关 96. Unique Binary Search Trees

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

小鱼儿/ 2022年03月07日 01:14/ 0 赞/ 147 阅读

相关【Leetcode】96. Unique Binary Search Trees

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

绝地灬酷狼/ 2022年02月20日 11:23/ 0 赞/ 163 阅读

相关 #96 Unique Binary Search Trees——Top 100 Liked Questions

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

ゝ一世哀愁。/ 2022年01月23日 06:13/ 0 赞/ 173 阅读

相关 Unique Binary Search Trees

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

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:29/ 0 赞/ 235 阅读