力扣刷题笔记：96.不同的二叉搜索树（动态规划，详细图解，必能看懂）

缺乏、安全感 2022-11-07 05:56 85阅读 0赞

## 题目： ##

96、不同的二叉搜索树

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

示例:

> 输入: 3  
> 输出: 5  
> 解释:  
> 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:  
> ![在这里插入图片描述][20210311162013139.png]

## 题解思路： ##

**1、思路**  
如果整数 1 ~ n 中的 k 作为根节点值，则 1 ~ k-1 会去构建左子树，k+1 ~ n 会去构建右子树。  
左子树出来的形态有 a 种，右子树出来的形态有 b 种，则整个树的形态有 a∗b 种。  
以 k 为根节点的 BST 种类数 = 左子树 BST 种类数 \* 右子树 BSTBST 种类数。

问题变成：不同的 kk 之下，等号右边的乘积，进行累加。

**2、定义 DP 子问题**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]  
（1）用 2、3 构建，和用 1、2 构建，出来的种类数是一样的，因为参与构建的个数一样。  
（2）再比如 2，3，4 和 1，2，3 都是连着的三个数，构建出的 BST 的种类数相同，属于重复的子问题。  
（3）定义 dp\[i\]：用连着的 i 个数，所构建出的 BST 种类数。

**3、状态转移方程：**

用 i 个节点构建 BST，除去根节点，剩 i-1 个节点构建左、右子树，左子树分配 0 个，则右子树分配到 i−1 个……以此类推。  
![在这里插入图片描述][20210311162357783.png]  
左子树用掉 j 个，则右子树用掉 i-j-1 个，能构建出 dp\[j\] \* dp\[i-j-1\] 种不同的BST。  
![在这里插入图片描述][20210311162440110.png]  
**4、基础条件**  
当 n = 0 时，没有数字，只能形成一种 BST ：空树。  
当 n = 1 时，只有一个数字，只能形成一种 BST ：单个节点。

> 时间复杂度 O(n^2)：有 n 个状态需要计算，计算每个状态又需要 O(n)。

## 题解python代码： ##

class Solution:
        def numTrees(self, n: int) -> int:
            G = [0]*(n+1)
            G[0], G[1] = 1, 1
    
            for i in range(2, n+1):
                for j in range(i):
                    G[i] += G[j] * G[i-j-1]
    
            return G[n]

> 作者：xiao\_ben\_zhu  
> 链接：[https://leetcode-cn.com/problems/unique-binary-search-trees/solution/shou-hua-tu-jie-san-chong-xie-fa-dp-di-gui-ji-yi-h/][https_leetcode-cn.com_problems_unique-binary-search-trees_solution_shou-hua-tu-jie-san-chong-xie-fa-dp-di-gui-ji-yi-h]  
> 来源：力扣（LeetCode）[https://leetcode-cn.com/problems/unique-binary-search-trees/][https_leetcode-cn.com_problems_unique-binary-search-trees]

[20210311162013139.png]: /images/20221023/fb8d514441934594a16bd7a780987354.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQxNDk0OA_size_16_color_FFFFFF_t_70]: /images/20221023/a829346df8b640479bbb57a1dfe90604.png
[20210311162357783.png]: /images/20221023/7abe366bbaa747cd8aac11e0180e4155.png
[20210311162440110.png]: /images/20221023/cee144c7dfe74d839b5e3b388f514329.png
[https_leetcode-cn.com_problems_unique-binary-search-trees_solution_shou-hua-tu-jie-san-chong-xie-fa-dp-di-gui-ji-yi-h]: https://leetcode-cn.com/problems/unique-binary-search-trees/solution/shou-hua-tu-jie-san-chong-xie-fa-dp-di-gui-ji-yi-h/
[https_leetcode-cn.com_problems_unique-binary-search-trees]: https://leetcode-cn.com/problems/unique-binary-search-trees/