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

悠悠 2023-07-02 04:24 94阅读 0赞

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3  
输出: 5  
解释:  
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1  
\\ / / / \\ \\  
3 2 1 1 3 2  
/ / \\ \\  
2 1 2 3

思路：dp\[n\]代表答案，则dp\[n\]=

左子树1节点，右子树n-1节点

左子树2节点，右子树n-2节点

................................

左子树n-1节点，右子树1节点

所有情况加起来。

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 = 1; j <= i; ++j) {
            dp[i] += dp[j - 1] * dp[i - j];
          }
        }
        return dp[n];
      }
    }

官方有一个数学，太强了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200125223834345.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

打卡每日一题!!! 今天为大家分享的还是一道动态规划类型的题目，可能猛地看起来有点像考察二叉树的知识，回归其本质还是动态规划的内容。题目描述： > 给你一个整数 n

我会带着你远行/ 2023年10月11日 17:53/ 0 赞/ 66 阅读

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

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

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

傷城~/ 2023年02月26日 11:23/ 0 赞/ 61 阅读

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

Leetcode 96. 不同的二叉搜索树 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-c

比眉伴天荒/ 2023年02月11日 07:10/ 0 赞/ 27 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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