96. 不同的二叉搜索树

女爷i 2022-12-23 06:18 100阅读 0赞

# 题目来源 #

[96. 不同的二叉搜索树][96.]

# 题目描述 #

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

# 题目解析 #

## 动态规划 ##

假设`n`个节点存在二叉排序树的个数是`G(n)`，令`f(i)`是以i为根的二叉搜索树的个数，则有

G ( n ) = f ( 1 ) + f ( 2 ) + f ( 3 ) + . . . f ( n ) G(n)=f(1)+f(2)+f(3)+...f(n) G(n)=f(1)\+f(2)\+f(3)\+...f(n)

n为根节点，当i为根节点时，其左子树节点个数为`[1,2,3...i-1]`，右子树节点个数为`[i+1, i+2，... n]`，所以当i为根节点时，其左子树节点个数为`i-1`个，右子树节点为`n-i`个，即`f(i) = G(i-1)*G(n-i)`。因此  
 G ( n ) = G ( 0 ) ∗ G ( n − 1 ) + G ( 1 ) ∗ G ( n − 2 ) + . . . + G ( n − 1 ) ∗ G ( 0 ) G(n) = G(0)\*G(n-1)+G(1)\*G(n-2)+...+G(n-1)\*G(0) G(n)=G(0)∗G(n−1)\+G(1)∗G(n−2)\+...\+G(n−1)∗G(0)

class Solution {
        
    public int numTrees(int n) {
        
            int [] ints = new int[n + 1];
            ints[0] = 1;
            ints[1] = 1;
            for (int i = 2; i <= n; i++){
        
                for (int j = 1; j <= i; j++){
        
                    ints[i] += ints[j - 1] * ints[i - j];
                }
            }
            
            return ints[n];
        }
    }

[96.]: https://leetcode-cn.com/problems/unique-binary-search-trees/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/9203002d0c944ada82a21b63a54d498c.png

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 101 阅读

相关算法：不同的二叉搜索树

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

红太狼/ 2022年04月10日 13:41/ 0 赞/ 146 阅读

相关【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 赞/ 115 阅读

相关不同的二叉搜索树

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

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