leetcode 96. 不同的二叉搜索树

旧城等待， 2022-02-16 05:01 115阅读 0赞

**递归**

**n个结点轮流做根节点，然后左右进行递归，两个结果做乘法**  
**发现20个就超int，打表只需要到19**

#include <iostream>
    #include <vector>
    using namespace std;
    
    class Solution { 
    public:
        int numTrees(int n) { 
            if(n==0){ 
                return 1;
            }
            if(n==1 || n==2){ 
                return n;
            }else{ 
                int ret = 0;
                for(int i=1;i<=n;i++){ 
                    ret+= numTrees(i-1) * numTrees(n-i);
                }
                return ret;
            }
            return 0;
        }
    };
    /* 打表 class Solution { public: int numTrees(int n) { vector<int> ret = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190}; return ret[n]; } }; */
    
    int main()
    { 
        Solution Solution1;
    
        cout << Solution1.numTrees(20) << endl;
        for(int i=0;i<20;i++){ 
            cout<<Solution1.numTrees(i)<<", ";
        }
        return 0;
    }

![在这里插入图片描述][2019042120264677.png]

[2019042120264677.png]: /images/20220216/21e8ed9174464b67b26c1d07168ca7de.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-96. 不同的二叉搜索树

题目来源 [96. 不同的二叉搜索树][96.] 递归 1.我们要知道二叉搜索树的性质，对于一个二叉搜索树，其【左边的节点值 < 中间的节点值 < 右边的节点值】

朱雀/ 2024年03月26日 18:36/ 0 赞/ 16 阅读

相关 leetcode96. 不同的二叉搜索树动归vs数学？

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二

悠悠/ 2023年07月02日 04:24/ 0 赞/ 47 阅读

相关 LeetCode 96不同的二叉搜索树&95不同的二叉搜索树Ⅱ

> 微信搜一搜：`bigsai` > [算法文章题解全部收录在github仓库bigsai-algorithm][github_bigsai-algorithm] >

谁借莪１个温暖的怀抱￠/ 2023年01月01日 10:54/ 0 赞/ 75 阅读

相关 96. 不同的二叉搜索树

题目来源 [96. 不同的二叉搜索树][96.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sha

女爷i/ 2022年12月23日 06:18/ 0 赞/ 101 阅读

相关 C语言重构【96】不同的二叉搜索树

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

亦凉/ 2022年12月21日 10:50/ 0 赞/ 92 阅读

相关 leetcode 96 不同的二叉搜索树

前言题目：[96. 不同的二叉搜索树][96.] 参考题解：[不同的二叉搜索树-代码随想录][-] -------------------- 提交代码这道

川长思鸟来/ 2022年09月16日 06:22/ 0 赞/ 102 阅读

相关【Leetcode】95~96 不同的二叉搜索树

Leetcode 95 不同的二叉搜索树 II 输入: 3 输出: [ [1,null,3,2], [3,2,null,1],

矫情吗；*/ 2022年03月07日 01:36/ 0 赞/ 128 阅读

相关 leetcode 96. 不同的二叉搜索树

递归 n个结点轮流做根节点，然后左右进行递归，两个结果做乘法发现20个就超int，打表只需要到19 include <iostream> includ

旧城等待，/ 2022年02月16日 05:01/ 0 赞/ 116 阅读

相关不同的二叉搜索树

题目给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不

今天药忘吃喽~/ 2022年02月09日 08:19/ 0 赞/ 148 阅读

相关 LeetCode : 96. Unique Binary Search Trees 二叉搜索树数量

试题 Given n, how many structurally unique BST’s (binary search trees) that store values

我不是女神ヾ/ 2021年06月24日 16:11/ 0 赞/ 282 阅读